剪绳子
题目描述
https://www.acwing.com/problem/content/24/
解题思路
令 \(dp[i]\) 定义为：绳子长度为 \(i\) 时的最大乘积
当绳长为 \(i\) 时，假设第一段长度为 \(j\)，则有剩下长度为 \(i - j\)，此时可分为两种情况：
- 继续剪：则有最大乘积为 \(j * dp[i - j]\)
- 不剪：则有最大乘积为 \(j * (i - j)\)
则有状态转移方程为：\(dp[i] = max(dp[i], j * (i - j), j * dp[i - j])\)
题解代码
class Solution {
public:
int maxProductAfterCutting(int length) {
int dp[length + 1] = {0};
for (int i = 2; i <= length; i ++ ) {
for (int j = 1; j < i; j ++ ) {
dp[i] = max({dp[i],j * (i - j), j * dp[i-j]});
}
}
return dp[length];
}
};