题目链接

牛客网

Leetcode

题目描述

把一根绳子剪成多段，并且使得每段的长度乘积最大。

n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

解题思路

Leetcode做过，使用dp，dp[i]表示i长度的绳子剪后乘积最大值（注意一定是剪了，否则n=2时应为2），剪多长和剩下的怎么处理（不剪或者剪）

public class Solution {
   
    public int cutRope(int target) {
   
        int[] dp = new int[target+1];
        dp[1] = 1;
        for (int i=2;i<=target;i++) 
            for (int j=1;j<i;j++)
                dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
        return dp[target];
    }
}