LeetCode 解题报告 (343, 377)- 动态规划求解数字的组合方案

发表于 标签 ，

LeetCode 上的这两道题 343. Integer Break 和 377. Combination Sum IV 从名字上来看没有什么联系，但是实际上两个题目都是通过动态规划来降低了求解时间复杂度，并且面对这种题目一开始往往难以往动态规划方向去想，特此记录。

对我而言，之所以不会一开始就想到动态规划，原因是这两个题目要求解的问题均是以某种方式构造某个数字时，总共的方案有几种或者最优的方案是哪种。一开始往往就是往数学或者 dfs 方向去想，而不会想到通过动态规划建立一个从 1 到目标数字的数组来记录各个状态的答案。

对于问题 343. Integer Break, 该问题属于求解组成某个数字的最优方案的问题，首先需要注意的是只把数字分为两部分，这样能够简化问题，然后对于这两部分都取最优时，则这两部分的乘积就是这种分法的最优解。那对于这两部分，可以很自然地想到均通过递归去求解最优，但是这种方法或导致很多重复的计算，比如说将 8 分为 6 和 2 时，需要计算 6 和 2 的最优解，但是进一步将 6 分为 4 和 2 时，还要计算 2 的最优解，这样显然会导致 多次计算 2 的最优解。

解决这个问题就是通过动态规划建立的数组记录数字 2 的最优解，需要求解时直接从数组中取即可，这时候动态规划的数组就有点类似 cache 的作用，实现的 java 代码如下，其中 dp[i] 表示数字 i 的最优解（即分解的数字的乘积最大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution 
{
    public int integerBreak(int n) 
    {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            int max = 0;
            for(int j = 1; j <= (i >> 1); j++)
            {
                max = Math.max( Math.max(dp[j], j) * Math.max(i - j, dp[i-j]), max);
            }
            dp[i] = max;
        }
        return dp[n];
    }
}

针对 LeetCode 的评测方法（建立一个对象，输入多组评测数据），上面的代码还能该继续优化，就是为这个对象建立一个全局的数组记录各个数字的最优解，供多组评测数据使用，当评测数字在数组中已经有答案了就不必再求解，反之递增数组。实现的 Java 代码如下，代码中的 cache list 与上面方法中的 dp 数组的作用相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution 
{
    private List<Integer> cache = new ArrayList<Integer>();
    public int integerBreak(int n) 
    {
        for (int i = cache.size(); i <= n; i++)
        {
            int max = 0;
            for(int j = 1; j <= (i >> 1); j++)
            {
                max = Math.max( Math.max(cache.get(j), j) * Math.max(i - j, cache.get(i-j)), max);
            }
            cache.add(max);
        }
        return cache.get(n);
    }
}

针对问题 377. Combination Sum IV，一开始想的是通过 dfs 来求解，但是题目中允许重复的数字，并且不同的顺序被认为是不同的组合方案，这样就使得如果通过 dfs 求解，时间复杂度会非常大。

通过动态规划求解，通过 dp 数组中的 dp[i] 表示数字 i 的组合方式的数目，可以同时解决上面提到的重复数字和数字的顺序问题。

则 dp[i+1] 可以考虑所有数字与已有的 dp[j] (j=0，1，...i) 的组合，实现的 Java 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution 
{
    public int combinationSum4(int[] nums, int target) 
    {
        int[] dp = new int[target+1];
        dp[0] = 1;
        Arrays.sort(nums);
        int count;
        for (int i = 1; i <= target; i++)
        {
            count = 0;
            for (int j = 0; j < nums.length; j++)
            {
                if (nums[j] > i) break;
                count += dp[i - nums[j]];
            }
            dp[i] = count;
        }
        return dp[target];
    }
}

往往会听到说动态规划的难点在构造递推关系，这没错，但是还有一个难点就是想到题目可以通过动态规划去求解，其实只要能往动态规划方向去想，递推关系往往也不难得到。因此，本文的主要作用还是要提醒面对这种求解目标数字的最优构造方案或者构造方案数目的时候，可以往动态规划方向去想，建立一个从 1 到目标数字的数组记录各个数字的结果，而不是仅仅拘泥于目标数字。