动态规划
思路详解:
设置一个数组dp[n+1]
,dp[ i ]
存储绳子长度为i
时的最大乘积。依题意,绳子至少被剪一次,所以绳子长度最小为2。外层for循环从绳长为i=2
的情况开始依次计算,直到计算到绳长为n
的情况。
内层for循环:当绳长为i
时,由于已知至少剪一刀,我们索性假设第一刀剪在长度为j
的位置(即第一段绳子长度为j)。剩下的那段长度为( i - j )
的绳子就变成了“可剪可不剪”。那究竟是“不剪了”得到的乘积大呢,还是“继续剪余下的这段”得到乘积更大?我们不知道,所以需要两种情况都计算一下进行比较。其中,“不剪了”得到的乘积是j * ( i - j )
,“继续剪”得到的乘积是j * dp[ i - j ]
。取其中的较大值,就是“第一剪在j位置”能得到的最大乘积。而第一剪的所有可能位置是1,2,…,i-1。依次计算所有可能情况,取最大值即为dp[ i ]
的值。
由上述过程可知,只有先依次计算出dp[2],dp[3],....的值,才能得到dp[n]的值。此为动态规划。
Java代码:
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n+1];
for(int i = 2; i <= n; 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[n];
}
}
突然仔细研究了下这类问题,如果写成一维的,dp[n]表示切成若干段的最大值,是这四个的最大值
如果写成二维,dp[i][j], 表示长度为i切成j段的最大值,就要四层循环了
表示长度 i-k 切成 l 段乘 长度 k 切成 j-l 段;但加的这个维度对这个题目没必要.....
tql
6
清晰明了,dpMark
这个不错,比官方解答一堆特判好
简单易懂,赞!
for(int j = 1 ; j <= i/2; j++)
我觉得j的遍历条件写成这样可以减少时间复杂度
赞
请问 为什么相同的编程思路 C却会算错 是因为C和Java的什么不同吗
这个是C++的代码,AC了,可以参考一下
因为Java出于安全性考虑,会自动为局部变量dp数组赋初值,但是C++是一个“随机值”。
棒棒哒
zan!
谢谢你的讲解
这个好,赞
这个很不错