动态规划，以LeetCode-CombinationSumIV问题为例

佚名 4年前 (2020-01-06) 算法 2009人围观抢沙发百度已收录

简介：

动态规划问题面试中经常遇到的问题之一，按照动态规划的一般定义，其一般解法在于将大问题分解为很多小问题去解决，但是我在遇到很多实际的问题时，想法都是强行的去将问题分解，而忽略了分解的必要性和途径的合理性。看某知乎大佬的帖子：动态规划的核心思想在于分解的小问题能否被上一级的问题去重用，也就是说我们在将大问题分解为小问题时，要考虑到求解出的小问题对于大问题的求解是否有一定的作用而且求解小问题的过程对大问题需要没有任何影响（像不像封装，似乎好多理论都是大同小异的，核心思想都很相似）。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

例子：

以LeetCode-Combination Sum IV问题为例：

题目是这样描述的：

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

是不是看起来感觉毫无难度，递归嘛，一层一层下去不就好了！所以我写出了递归求解思路：

1 private int combinationSum4_recur(int[] nums, int target){
2         int sum = 0;
3         for(int i : nums){
4             if(i == target) sum += 1;
5             else if(i < target) sum += combinationSum4_recur(nums, target - i);
6         }
7         return sum;
8 }

和我们用脑子解决这个问题的思路一模一样，然后就TLE了。。。

出错的例子：nums={2,1,3} target=35，我日哦，如果用大脑去解决，你得想吐了。

所以我需要想想这是为什么，首先1+1，然后+1，然后+1.。。。。。然后好多好多+1，emmmm，出来了一个35的方案了，然后下一轮首先1+1，然后+1，然后+1.。。。。。然后好多好多+1再+3。等一下前面的1+1+1什么的是不是很熟悉！我们为什么不把它记住呢！所以，dp[]来了！

dp[]数组是什么呢，它是一个长度为target+1的int数组，首先，0为1；它的意思就是默认nums数组中组合为0的可能方式设定为1.然后，dp[1]等一系列元素我们暂时设置为-1，表示还未进行计算。这样，由顶而下的动态规划就出来了，我们将求解一个巨大的target分解为求解一个较小的target，而求解这个较小的target又会被分解为求解一个更小的target。。。。。。直到最后，而在这过程中，求解出来的target我们都存储在了dp数组中！那么求解到最后，我们岂不是一直进行数组的调用就可以了！只进行了很少的计算！代码如下：

 1 private int combinationSum4_dp(int[] nums, int target){
 2         dp = new int[target + 1];
 3         Arrays.fill(dp, -1);
 4         dp[0] = 1;
 5         return helper(nums, target);
 6 }
 7 
 8 private int helper(int[] nums, int target){
 9         /**
10          * dp记录到达索引指示的target有几种方案去解决
11          * 就是相当于记住它的中间结果！！！
12          */
13         if (dp[target] != -1) {
14             return dp[target];
15         }
16         int res = 0;
17         for (int i = 0; i < nums.length; i++) {
18             if (target >= nums[i]) {
19                 res += helper(nums, target - nums[i]);
20             }
21         }
22         dp[target] = res;
23         return res;
24}