動態規劃入門，從簡單遞歸到記憶化搜索到動態規劃
打家劫舍
class Solution {private int nums[];public int rob(int[] nums) {this.nums = nums;return dfs(nums.length - 1);}public int dfs(int i){if (i < 0){return 0;}int res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);return res;}
}
思路：
首先看到題目可以轉換到當前這個位置選擇或者不選的場景，比如說，首先我們選擇了第一個，那么下一次能選擇的第一個是第三個，如果不選第一個的話，下一個能選擇的就是第二個.
注意點
- 對于結束的地方，剛開始大家可能會想著這個時候會是結束的地方，需要返回中的sum結果，但是我們需要知道這個地方返回的是當前位置能有的收益是多少，如果當前這個位置已經 < 0,那么這時候結果就是0。
- int res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]); 這代表我們在當前i的這個位置能有的兩種情況，對于第一種情況，表示在當前這個位置我們不進行選擇，可以在下一個位置進行選擇。第二種情況表示我們選擇了當前這個位置，體現在將當前的收益進行相加，下一次能選擇的第一個位置就是dfs（i - 2），最后選擇這兩種情況的最大值。
- 返回res的結果。
上述情況會超時，我們分析一下是哪些時候會重復計算：
上述情況中，可以看到2的這種情況會重復計算，我們可以在計算得到2的結果之后，將2的結果保存到map中或者數組中，這樣下次需要2的結果的時候直接從map中進行查找就可以，這時候O（1）的時間就可以獲得。
記憶化搜索
class Solution {private int nums[];HashMap<Integer,Integer> hashmap = new HashMap<>(); // 記憶化數組public int rob(int[] nums) {this.nums = nums;return dfs(nums.length - 1);}public int dfs(int i){if (i < 0){return 0;}if (hashmap.containsKey(i)){ // 如果當前這個位置之前已經算過，直接去記憶化數組中拿return hashmap.get(i);}int res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);hashmap.put(i,res); // 每次計算一個結果 就將當前的結果存入到記憶化數組中return res;}
}
和上面的代碼優化的地方就是加入了一個記憶化數組，如果一個位置的結果計算過，就將結果存入到記憶化數組中，之后需要這個結果的時候，就從記憶化數組中進行獲取。
從記憶化搜索到動態規劃
我們使用圖示的方法：
步驟
1、首先查看dfs中有多少個可變的變量（有時候，有些參數是固定的，不會發生變化）。比如說這里我們只有一個參數，我們就生成一個一維表。
2、找到已知條件。動態規劃的題目都是可以從一些給定的點，逐步得到最后的結果，比如說給定0，我們可以推到1，得到1，可以推出2，得到2，可以推出 3，之后逐步獲得答案。那么我們需要如何得到這些已知條件。
答案就是我們可以看basecase，也就是dfs遞歸的出口，我們觀察到當i < 0 的時候，對應的結果都是0。另外我們觀察到我們需要兩個參數，所以我們取出 -1 和 -2 得到 dfs（0）
dfs（0）= max（dfs（-1），dfs(-2) + nums[0]）= 1
dfs（1）= max（dfs（0），dfs(-1) + nums[1]
。。。。。
依次可以得到最終的dfs（4），這個dfs（4）就是我們需要的最終結果。
class Solution {int nums[];private int res[];public int rob(int[] nums) {this.nums = nums;res = new int[nums.length + 2];res[0] = 0;res[1] = 0;for (int i = 2;i < res.length;i++){res[i] = Math.max(res[i - 1],res[i - 2] + nums[i - 2]);}return res[res.length - 1];}
}
超過100%
我們聲明可一個結果數組，這個結果數組是一維的，正如我們上面討論的一樣，可變參數有幾個，就聲明一個幾維的數組，初始的時候將數組的第一個和第二個設置成0，之后依次填充數組，返回最后一個結果。
希望對看到這里的你有一點點幫助！
