题解 | #剪绳子#

public:
    int cutRope(int number) {
        // 直接递归。
        // 5 = 1+4=2+3 所以，5的结果 应该是1和4最大的结果相乘 或者2和3最z的结果相乘
        
        // 再比如20 =1+19 = 2+18.... 所以结果就是1和19的最大值相乘，或者2和18的最大值相乘，或者3和17最大值相乘。。。
        if(number == 2)
            return 1;
        if(number==3)
            return 2;
        vector<int>dp(number+1);
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        for(int i=4;i<=number;i++)
        {
            int temp=0;
            for(int j=1;j<=i/2;j++)
            {
                temp=max(temp,dp[j]*dp[i-j]);
            }
            dp[i]=temp;
        }
        for(int i=0;i<=number;i++)
            cout<<dp[i]<<" ";
        return dp[number];
    }
};