動態規劃的核心思想 -- 以空間換時間
復雜點說通過分解問題為子問題并存儲子問題解來優化復雜計算的算法策略。
簡單看個問題。
一，初始：求最長連續遞增子序列
nums = [10,9,2,5,3,7,101,18]求上面數組中的最長連續遞增子序列，輸出其長度
暴力解法中我們需要以每個數為開頭去遍歷數組，得到最長的子數組。
會產生如下遍歷
3,7,101
7,101
可以看到，有重復的計算。我們先用java寫一下暴力解法。
暴力解法
public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int res = 0;for (int i = 0; i < nums.length; i++) {int temp = 1; // 當前子序列的長度，初始為1（單個元素）for (int j = i + 1; j < nums.length; j++) {if (nums[j] > nums[j - 1]) {temp++;} else {break;}}res = Math.max(res, temp); // 更新最長子序列的長度}return res;}雙重for循環，時間復雜度為 (O(n^2))，空間復雜度為 (O(1))。
動態規劃
初始化dp的int數組。值為到當前位置的最大連續數。這樣整個遍歷完dp數組的值應該是
[1,1,1,2,1,2,3,1]。 可以看到最大長度為3。
/*** 方法二： 動態規劃求解連續遞增子序列* @param nums* @return*/public int lengthOfLIS2(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n];dp[0] = 1; // 單個元素本身就是一個長度為 1 的連續遞增子序列int res = 1; // 初始化結果為 1for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;} else {dp[i] = 1; // 當前元素本身可以作為一個新的連續遞增子序列的起點}res = Math.max(res, dp[i]); // 更新最長子序列的長度}return res;}時間復雜度：(O(n))
空間復雜度：(O(n))
二，升級：求最長遞增子序列
nums = [10,9,2,5,3,7,101,18]求上面數組中的最長遞增子序列，輸出其長度
將上面一道題進行稍微變化一下，我們可以看出，現在的結果應該是2,3,7,101。輸出結果應該是4。
如果不用動態規劃，這道題有點難解。需要用到回溯+記憶，單純的暴力解法并不適用。
比如我再加一個測試用例
nums?=[0,1,0,3,2,3]
?回溯法
/*** 方法一： 暴力解法* @param nums* @return*/public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) return 0;int maxLen = 0;for (int i = 0; i < nums.length; i++) {maxLen = Math.max(maxLen, backtrack(nums, i, new ArrayList<>()));}return maxLen;}// 回溯法生成所有遞增子序列private int backtrack(int[] nums, int index, List<Integer> current) {if (index >= nums.length) return current.size();int maxLen = current.size(); // 不選當前元素的默認長度// 選擇當前元素的情況if (current.isEmpty() || nums[index] > current.get(current.size() - 1)) {current.add(nums[index]);int lenWith = backtrack(nums, index + 1, current);current.remove(current.size() - 1);maxLen = Math.max(maxLen, lenWith);}// 不選當前元素的情況int lenWithout = backtrack(nums, index + 1, current);return Math.max(maxLen, lenWithout);}時間復雜度： (O(2^n))
空間復雜度：O(n)
該方法容易超過時間限制
動態規劃
這個就需要在上個動態規劃樣例中稍微改動一下。
我們先模擬一下對照樣例生成的dp數組應該的樣子。
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
int[] dp = {1, 1, 1, 2, 2, 3, 4, 4};
先舉個簡單的方便觀察的例子
int[] nums = {1, 2, 3, 4, 2, 6, 7};
int[] dp = {1, 2, 3, 4, 1, 5, 6};
即便當數組為遞減數組時，長度也會輸出1
- 所以我們還是需要先將dp數組全部初始化1
- 第一次遍歷，2 > 1的，所以dp[1] = dp[0] + 1;
- 第二次遍歷，3 > 1的，所以dp[2] = dp[0] + 1; 然后 3 > 2的，所以?dp[2] = dp[1] + 1；
- ……
- 第五次遍歷，6 > 4的，所以dp[5] = dp[3] + 1;但是6 > 2，不能得出dp[5] = dp[4] + 1,需要dp[4] + 1與當前的dp[5]的值進行比較。取最大的一個。
- ……
所以綜上我們可以寫出代碼
/*** 方法二： 動態規劃求解遞增子序列* @param nums* @return*/public int lengthOfLIS2(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, 1);int res = 1; // 初始化結果為 1for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}res = Math.max(res, dp[i]);}}return res;}?時間復雜度為 ?O(n2)，空間復雜度為 ?O(n)。
三，再升級：刪除最少元素，使剩余元素先遞增后遞減
動態規劃
還是以剛剛的例子為例
nums = [10,9,2,5,3,7,101,18]刪除最少元素，使剩余元素先遞增后遞減，輸出最少需要刪除多少元素。
?通過上面兩個例子，我們可以看出一個dp數組只能保存一個狀態。
對于這道題，我們可以考慮使用兩個dp數組來完成。
nums = [10,9,2,5,3,7,101,18]int[] dp1 = {1, 1, 1, 2, 2, 3, 4, 4}; //遞增dp int[] dp2 = {4, 3, 1, 2, 1, 1, 2, 1}; //遞減dp
?可以看出在dp1[6] + dp2[6] = 6的時候是最大的，所以最大長度應該是dp1[6] + dp2[6] - 1 = 5；
因為6這個節點重復計算了，所以需要減1
那么就能得出答案需要刪除：nums.length() - 5 = 3;
最少需要刪除3個元素。
/*** 方法二： 動態規劃求解刪除最少元素，使剩余元素先遞增后遞減* @param nums* @return*/public int lengthOfLIS3(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp1 = new int[n];int[] dp2 = new int[n];Arrays.fill(dp1, 1);Arrays.fill(dp2, 1);// 遞增子序列for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp1[i] = Math.max(dp1[i], dp1[j] + 1);}}}// 遞減子序列for (int i = n - 2; i >= 0; i--) {for (int j = n - 1; j > i; j--) {if (nums[j] < nums[i]) {dp2[i] = Math.max(dp2[i], dp2[j] + 1);}}}// 合并int max = 0;for (int i = 0; i < n; i++) {if (dp1[i] + dp2[i] > max) {max = dp1[i] + dp2[i];}}return n - max - 1;}?四，看一道力扣原題
322. 零錢兌換
?這道題可以換個角度看看，我們要求amount的最小硬幣個數。可以構建dp[amount + 1]數組，
求從1 - amount間的所有最小個數。
換個簡單的實例
輸入：coins = [1, 2], amount = 5
以外層coins為循環，內層循環amount得到最小值
如上面例子。
初始化dp數組，因為要求最小，所以初始值應該為最大，且dp[0] = 0;
第一次外層循環1得到dp數組[0,1,2,3,4,5]
第二次外層循環2得到dp數組[0,1,1,2,2,3]
構建dp公式：
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
?得到解法
public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1); // 初始化為不可達標記dp[0] = 0; // 基礎情況// 外層循環遍歷硬幣for (int coin : coins) {// 內層循環遍歷金額（完全背包正序遍歷）for (int i = coin; i <= amount; i++) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}return dp[amount] > amount ? -1 : dp[amount];}
