題型：從數組中選擇不相鄰元素，求和最大
（1）對于數組中的每個元素，都存在兩種可能性：（1）選擇（2）不選擇，是以對于這類問題，暴力方法（遞歸思路）的時間複雜度為：O(2^n)；
（2）遞歸思路中往往會包含大量的重複計算，從時間角度出發，我們一般都會使用動态規劃的方法來解決這類問題；而動态規劃的核心思想就是：使用變量或者數組來記錄重複出現的部分，這樣會大大減少計算量，節省時間。
（3）在使用動态規劃的方法解決這類問題時，一般過程是：
- 最好先使用暴力分析的方法，按照題意将原題中給出的案例推導出來，然後從中總結規律，便于分析出狀态轉移方程
- 定義DP狀态，儲存中間變量
- 寫出狀态轉移方程
打家劫舍（leetcode 198）
分析：
（1）對于每個數組元素，都有兩種選擇：選與不選
（2）DP狀态：opt[i] 表示：偷到第 i 間房屋時，小偷可以偷到的最大金額
（3）分析狀态轉移：
選： opt[i] = opt[i-2] + nums[i]
不選： opt[i] = opt[i-1]
則，opt[i] = max( opt[i-2] + nums[i], opt[i-1])
python代碼實作：
1 class Solution:
2 def rob(self, nums: List[int]) -> int:
3 n = len(nums)
4 if n == 0: return 0
5 elif n < 2: return max(nums)
6 else:
7 opt = [0 for i in range(n)]
8
9 opt[0] = nums[0]
10 opt[1] = max(nums[0], nums[1])
11
12 for i in range(2, n):
13 opt[i] = max(opt[i-1], opt[i-2]+nums[i])
14
15 return opt[-1] View Code
打家劫舍（leetcode：213）
分析：
（1）213與198相比，不同之處：198是首尾不相連的數組，213是首尾相連成環的數組；
（2）在開始做這個題的時候，很容易陷入一個誤區：首尾相連成環，就必須得從環的角度出發來解決這個問題，這往往需要考慮很多的邊界問題，而且很容易解出來。在這個時候，我們不防轉換一下角度，聯想一下之前做過的類似題目的思路（198），找一下可以借鑒的部分。
（3）環：首尾相連，每個位置的元素等同，不分初始位置和結束位置，但是環可以拆成首尾不相連的數組形式（198題）；
（4）要求是：選擇的元素不相鄰，是以，現在分為兩種情況：1. 選擇第一個位置的房屋金錢（不能選擇最後一個位置的房屋金錢） 2. 選擇最後一個位置的房屋金錢（不能選擇第一個位置的房屋金錢），從這個角度就可以将環分成兩個首尾不相連的數組形式，再使用198的思路進行求解；
python 代碼實作：
1 class Solution:
2 def rob(self, nums: List[int]) -> int:
3 n = len(nums)
4 if n == 0: return 0
5 elif n <= 3: return max(nums)
6 else:
7 nums_1 = [nums[i] for i in range(n-1)]
8 nums_2 = [nums[i] for i in range(1, n)]
9
10 opt1 = [0 for i in range(n)]
11 opt2 = [0 for i in range(n)]
12
13 opt1[0], opt2[0] = nums_1[0], nums_2[0]
14 opt1[1], opt2[1] = max(nums_1[0], nums_1[1]), max(nums_2[0],nums_2[1])
15 for i in range(2, n-1):
16 opt1[i] = max(opt1[i-1], opt1[i-2]+nums_1[i])
17 opt2[i] = max(opt2[i-1], opt2[i-2]+nums_2[i])
18
19 return max(max(opt1), max(opt2)) View Code
打家劫舍（leecode：337）
分析：
（1）337是二叉樹形式的數組，條件仍然是：選擇的元素不相鄰；
（2）從根節點出發，（選擇的元素不相鄰）其實是：不能同時選擇父節點和子結點上的元素，但是可以選擇兄弟節點，可以選擇爺孫節點；
（資料結構中的樹模型還沒複習到，等複習完樹模型之後再回來整理這個題的代碼~~）
轉載于:https://www.cnblogs.com/xdliyin/p/10779134.html