动态规划 Leetcode 343 整数划分

整数划分

Leetcode 343

学习记录自代码随想录

要点：1.递推公式要想到，从2开始找规律；

class Solution {
public:
    int integerBreak(int n) {
        
        // 1.dp[i]代表输入i的最大乘积
        vector<int> dp(n+1, 0);
        // 2.递推公式dp[i] = max(j*dp[i-j], k*(i-k), dp[j]*dp[i-j]) j = 1:i/2, k = i/2
        
        // 3.dp数组初始化
        dp[2] = 1;
        
        // 4.遍历顺序，从前向后
        for(int i = 3; i < n+1; i++){
            dp[i] = (i / 2) * (i - i / 2);
            for(int j = 1; j <= i/2; j++){
                int max_number = max(j*dp[i-j], dp[j]*dp[i-j]);
                dp[i] = max(dp[i], max_number);
            }
        }

        // 5.举例推导dp数组
        return dp[n];
    }
};