LeetCode·343.整数拆分·动态规划

链接：https://leetcode.cn/problems/integer-break/solution/-by-xun-ge-v-y5f9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路

• 确定dp数组（dp table）以及下标的含义

dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

• 确定递推公式

可以想 dp[i]最大乘积是怎么得到的呢？

其实可以从1遍历j，然后有两种渠道得到dp[i].

• 一个是j * (i - j) 直接相乘。
• 一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。

• dp数组初始化

对于任意一个n(n > 1)，我们肯定可以将其拆分为 1 和 n-1 ，所以对于任意一个dp都可以初始化为 n-1

• 确定遍历顺序

确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

枚举j的时候，是从1开始的。i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。

• 动态更新dp数组

代码

#define MAX(a, b, c) (((a) > (b) ? (a) : (b)) > (c) ? ((a) > (b) ? (a) : (b)) : (c))
 
int integerBreak(int n){
    int dp[n+1];
    for(int i = 2; i <= n; i++)//枚举需要拆分的数
    {
        dp[i] = i-1;//初始化
        for(int j = 1; j < i - 1; j++)//枚举并更新动态数组
        {
            dp[i] = MAX(j * (i-j), j * dp[i-j], dp[i]);
        }
    }
    return dp[n];
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/integer-break/solution/-by-xun-ge-v-y5f9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。