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

1053 0 0

作者:后会丶无期

简介：

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

例子：

以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}

是不是清晰很多，我们首先进行了较小target的组合数，然后依次往大再往大。。。。。。这样到最后我们就解决了那个看似很大的target。这不就是动态规划的思想吗！

所以以后首先要找到大问题和小问题之间共有的特性，列出一定的状态转移规律，然后设计满足条件的小问题解决方案，最后凭借记忆中的中间值快速求出最终解！

当然动态规划问题极多，有待后续继续进步。。。。。。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/lybnumber6/p/12158901.html

标签：算法数据结构 LeetCode

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

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