LeetCode 343. 整数拆分（动态规划）

LeetCode 343. 整数拆分

思路：

通过题目我们可以知道，一个正整数最少拆成2个数，最多拆成n个数，即可拆分的个数为2～n

若将拆除的第一个正整数令为k，那么剩下的数则为n-k，此时可以不拆分，也可以继续拆成2～n-k个，若我们可以计算出n-k拆分后的最大乘积，则在此基础上很容易得出n拆分后的最大乘积。此时容易想到使用动态规划的思想，通过不断求解子问题的最优解来确定原问题的最优解

那么，我们令dp[i]为正整数i拆分后的最大乘积（最少拆成2个，最多拆成i个）

dp[0]，dp[1]无意义，不必初始化，则初始化dp[2]=1

此时可以将i从3开始遍历到n，来计算每个正整数拆分后的最大乘积dp[i]
在每个数i的遍历过程中，可以将i先拆分出j，则剩下的为i-j，则有

dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j))
1

即，可以将i只拆分成j和i-j两个数，此时乘积为i*(i-j)
也可以将i先拆分成j，剩下的i-j继续拆分，此时乘积为j*dp[i-j]
取其中的最大乘积即为dp[i]

最后，dp[n]即为n拆分后所有数的最大乘积

代码：

#include
#include
#include
#include
using namespace std;

class Solution {
public:
    int integerBreak(int n) {
        int dp[60];
        memset(dp, 0, sizeof(dp));
        dp[2]=1;
        for(int i=3;i<=n;++i)
            for(int j=1;j<i;++j)
                dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
        return dp[n];
    }
};

int main()
{
    int target = 10;
    Solution *solution = new Solution();
    int ans=solution->integerBreak(target);
    printf("%d\n",ans);
    free(solution);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

总结： 做这道题时，没有想清楚dp[i]的定义，错误地认为dp[i]就是最大乘积（不论何种情况，是拆分，还是没拆分），所以写成了dp[i]=max(dp[i],dp[i-j]*j)，没有想清楚dp[i]是拆分后的最大乘积，即这个代码表示的是拆分成3个或者更多个数后的最大乘积，把dp[i]拆分为两个数的情况给 遗漏了。。。

参考链接：https://blog.csdn.net/zhizhengguan/article/details/124453544