AcWing 25. 剪绳子 dp
原题链接
中等
作者:
思念是一种病
,
2021-08-13 19:50:41
,
所有人可见
,
阅读 749
class Solution {
public:
/*
平心而论,这题很难
我想不到贪心的做法,隐隐约约觉得这是dp可以处理的问题
但是又不知道如何去处理
第一反应是和 钢条切割很像
*/
int maxProductAfterCutting(int length) {
vector<int> dp(length+1);
/*
dp[i]指的是 长度为i的数字 所能整出来的最大乘积
首先要切第一刀 因为题目规定 起码要切一刀
假设这一刀切在了j这个位置
那我们的最大值就是
要么剩下的不切
j*(i-j) or j*dp[i-j]
其中i-j 一定不等于 dp[i-j] 因为题目规定 必须要切一刀
但是由于我们已经切了第一刀了
导致后面的部分 就是可以切 也可以不切了
*/
dp[1]=1;
for(int i=2;i<=length;i++)
for(int j=1;j<=i;j++)
{
dp[i]=max(dp[i],max(j*dp[i-j],j*(i-j)));
}
return dp[length];
}
};
大佬,第二层循环是不没有等号
666