剑指OFFER 剪绳子

剑指OFFER 剪绳子

class Solution {
public:
    int cutRope(int number) {
        //最少要剪一次,所以前面的dp数据有点特别
        if(number == 1)return 1;
        if(number == 2)return 1;
        if(number == 3)return 2;
        
        vector<int> dp;
        dp.resize(number + 1);
		
        //这里是不需要再剪的数据,这里可能会多余一两个数据,但是没有关系,都写上
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;

        for(int i=4;i<=number;i++)
        {
            for(int j=1;j<=i/2;j++)
            {
                dp[i] = max(dp[i-j]*dp[j],dp[i]);
            }
        }

        return dp[number];
    }
};