剑指 Offer.14-I.剪绳子

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;  //当绳子的长度为2有1中剪法
        for(int i=2;i<=n;i++){
            // 计算当前绳子最长的乘积
            for(int j=1;j<i;j++){
                // 从1开始切分绳子，判断是右部分直接乘大，还是剪开之后乘大
                int newbig = Math.max(j*(i-j),j*dp[i-j]);
                // 每更新一种剪法就要更新当前长度乘积的最大值
                dp[i] = Math.max(dp[i],newbig);
            }
        }
        // 放回动态规划计算出的最优解
        return dp[n];
    }
}