题解 | #剪绳子#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // write code here
        if(n<=3){
            return n-1;//2分为1 1 3分为 1 2
        }
        vector<int>dp(n+1);
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;//2 和3此时的值是不剪绳子的最大值 用于后面进行计算 符合题意的结果已经在上面返回了
        dp[4]=4;
        for(int i=5;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i]=max(dp[i],j*dp[i-j]);
            }
        }
        return dp[n];
    }
};