题解 | #剪绳子#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // write code here
        if(n<=3)
            return n-1;
        vector<int> dp(n+1,0);

        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=4;

        for(int i=0;i<=n;i++)
            for(int j=1;j<i;j++)
                dp[i]=max(dp[i],j*dp[i-j]);
        return dp[n];
        
    }
};