[动态规划] Leetcode 343. 整数拆分_分月饼leetcode

[动态规划] Leetcode 343. 整数拆分

题目

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路

• 确定dp数组含义：dp[i]:分解数字i,可以得到的最大乘积dp[i]
• 确定状态转移方程：采用定1移2的方法：外层循环遍历i,对于每一个dp[i],再次从1开始遍历，遍历到i - 2,有两种渠道获得dp[i],一个是j * (i - j)（i - j不能再次拆分，比如i - j = 2）,另一个是j * dp[i - j],相当于拆分(i - j),dp[i] = max(dp[i],max(i * (i - j),dp[i - j] * j))
• dp数组的初始化：dp[2] = 1,其余都是没有意义的
• 确定遍历顺序：从前向后进行遍历

代码

class Solution {
public:
    int integerBreak(int n) {
        // 定义dp数组
        vector<int> dp(n + 1);
        dp[2] = 1;// 初始化dp[2]

        for(int i = 3; i <= n; i++)
        {
            for(int j = 1; j < i - 1; j++)
            {
                // 状态转移方程
                // 定一移二  对于每一个dp[i] 循环遍历j j是从1开始遍历到 i - 2 正好得到dp[2]
                dp[i] = max(dp[i],max(j * (i - j),j * dp[i - j]));
            }
        }

        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20