動態規劃，以LeetCode-CombinationSumIV問題為例-有解無憂

簡介：

動態規劃問題面試中經常遇到的問題之一，按照動態規劃的一般定義，其一般解法在于將大問題分解為很多小問題去解決，但是我在遇到很多實際的問題時，想法都是強行的去將問題分解，而忽略了分解的必要性和途徑的合理性，看某知乎大佬的帖子：動態規劃的核心思想在于分解的小問題能否被上一級的問題去重用，也就是說我們在將大問題分解為小問題時，要考慮到求解出的小問題對于大問題的求解是否有一定的作用而且求解小問題的程序對大問題需要沒有任何影響（像不像封裝，似乎好多理論都是大同小異的，核心思想都很相似），

例子：

以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.uj5u.com/qita/113033.html

標籤：其他

上一篇：Python - 八大排序演算法

下一篇：深度學習專案實戰視頻課程-人臉檢測