1、前言
题目描述
2、思路
这道题用动态规划做。
1、我们想要求 n 被剪掉后的最大面积，只需要求比 n 小的剪掉后的最大面积
2、我们使用 dp[n] 表示 0 - n 的绳子的最大面积，因为小于2的都是0、1，所以直接从2开始
3、假如绳子为 i 米，被剪成2段，第一段是 j 米；第二段可以剪也可以不剪，如果不剪，那么面积为 j * (i - j)，如果减，那么面积为 j * dp[i - j]，取最大即可
4、那么 i 米的最大值，即为 max(dp[i], max(j * (i - j), j * dp[i - j]))
3、代码
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 3; i <= n; i++){
for(int j = 2; j <= i; j++){
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
网友评论