leetcode 343. 整数拆分

分析

1. 状态表示：

   · dp[i] 表示整数 i 拆分乘积的最大值。

2. 转移方程：

   · 对于每个数字 i 都进行一遍循环，计算 (i - j) * j，(j <= i - 1)，并求其与 dp[i]，dp[i - j] * j 的最大值，即：dp[i] = max(dp[i]，(i - j) * j，dp[i - j] * j)

   · 与 dp[i - j] * j 比较是因为 i - j 可能小于 i - j 拆分的乘积。

3. 边界：

   · 输入的整数 n 大于等于 2，考虑到会拆分成类似 (i - 1) * 1 等类型，故dp[1] = 1

实现

class Solution {
public:
    int integerBreak(int n) {
        int dp[n + 1];
        memset(dp, -1, sizeof(dp));

        dp[1] = 1;

        for(int i = 2; i <= n; ++i) {
            for(int j = 1; j <= i - 1; ++j) {
                dp[i] = max(dp[i], dp[i - j] * j);
                dp[i] = max(dp[i], (i - j) * j);
            }
        }

        return dp[n];
    }
};

小结

1. 确定状态转移的方式：想求dp[i]，应先求dp[i - j]，(j <= i - 1)
2. 确定状态转移方程：明确拆分时的可能乘积，本题有两个 (i - j) * j 和 j * dp[i - j]
3. 确定边界