题目描述

https://www.acwing.com/problem/content/24/

解题思路

令 \(dp[i]\) 定义为：绳子长度为 \(i\) 时的最大乘积

当绳长为 \(i\) 时，假设第一段长度为 \(j\)，则有剩下长度为 \(i - j\)，此时可分为两种情况：

1. 继续剪：则有最大乘积为 \(j * dp[i - j]\)
2. 不剪：则有最大乘积为 \(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];
    }
};