LeetCode 198. House Robber

題目描述：

你是一個強盜，需要搶劫這一排屋子，但是如果連續搶兩間，那麼警報系統會開啟，那麼在不觸碰到警報系統的條件下，能夠搶到的最大金額會是多少？

TestCase:

nums = [1,2,3,1] 答案是4 = (1+3) //都沒有觸動警報

nums = [2,0,0,2]答案是4 = (2+2) // 都沒有觸動警報

那麼這題的解法也可以使用DP來解決：

DP的核心概念：使用前一次的計算結果當作下一次計算的基礎

透過建立Array的方式來儲存計算結果

我建立一個 N x 2 （Row x Col）的陣列來儲存結果，那麼邏輯該怎麼編排？

初始的值：

Array[0][0] = 0 // 因為沒有上一回合最大，所以儲存0

Array[0][1] = nums[1] // 因為沒有前一個可以比較，所以直接設定為nums[1]，也代表從nums[1]開始

邏輯過程：

因為不能觸動警報（代表不能使用連續的index），所以我要讓index間隔

Row[0]為休息區，來儲存上一回合最大(Array[i-1][1])，在每一輪的Row[0]都不會參與本次的計算當中，會休息一回合，在下一回合才會被取用

Row[1]為一個比較區，出現兩種狀況：

• 這次走到的Value ＋ 上(上次的結果) // 因為是這一次跟上上一次，所以不會觸動警報
• Array[i][1] = nums[i] + Array[i-1][0]
• 上一次的結果 // 如果是採用上一次的結果，那麼代表這一次並不會被採用，所以也是相隔了兩個
• Array[i][1] = Array[i-1][1]

兩個去比較哪個會是比較大的數，作為這一輪比較的結果（DP概念，使用上一次的計算結果作為這一次的計算基礎）

現在搭配一點程式碼來理解：

func houseRobber(_ nums:[Int]) -> Int{
guard nums.count >0 else{ return 0 }

// 建立一個儲存結果的Dp Array
let dp:[[Int]] = Array(repeating:Array(repeating:0,count:2),count:nums.count)

dp[0][0] = 0 // 因為沒有上(上次)的結果，所以為0
dp[0][1] = nums[1] // 因為沒有上次的計算結果，所以直接帶入為nums[1]

for i in 1..<nums.count{
   dp[i][0] = dp[i-1][1] // 儲存上一輪的最大計算結果，這一輪不會用到
   dp[i][1] = max(dp[i-1][0] + nums[i],dp[i-1][1])
   // 比較上一回合的儲存區（上上回合的最大)＋這一回合的數字 VS 上一回合的最大
}

return max(dp.last![0],dp.last![1])
}