歡迎關(guān)注本人的微信公眾號AI_Engine

題目1：你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 1:

輸入: [1,2,3,1]

輸出: 4

解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

示例 2:

輸入: [2,7,9,3,1]

輸出: 12

解釋: 偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。

答案：

分析：打家劫舍這道題目是動態(tài)規(guī)劃中的簡單題，但是個人覺得還是蠻有意思的，所以今天的主題就是將一些有意思的題目做以分享，也希望大家能喜歡。打家劫舍這道題在近兩年作為面試題出現(xiàn)的公司有百度，騰訊，谷歌，微軟，網(wǎng)易等等，這樣看來互聯(lián)網(wǎng)公司面試的時候還是比較open的哈。這道題還是先往簡單的情況分析（題目降維），即如果只有一個房屋可以打劫的時候，顯然最大值就是第一個房屋內(nèi)的金額。當(dāng)用f(n)表示從前面n個房屋中獲取的最大金額，則f(1) = nums[0]。同理f(2) = max(nums[0], nums[1])。當(dāng)房屋變成3個的時候情況發(fā)生了變化，就是小偷可能要思考一下我偷不偷第3個房屋的錢，如果偷了，那么第二個房屋的錢我就不能偷。也就是說他為了爭取利益最大化，就要在只偷第2個房屋的錢和偷1和3房屋的錢之間進行比較大小，這樣得出的答案就是在有3個房屋的情況下能獲得的最大金額?，F(xiàn)在房屋變成了4個，小偷現(xiàn)在又要合計了，如果我偷第4個房屋的錢，那第三個房屋的錢我就不能碰，這樣我就需要將只有2個房屋情況下的最大收益與第4個房屋的收益進行求和，然后與我不偷第4個房屋情況下的收益（就是只有3個房屋可偷的情況下的收益）進行比較大小。經(jīng)過這樣的迭代，就會將從1到n個房屋的情況下的最大收益記錄下來，然后返回出記錄表里的最后一個元素就是最大值了。而這個記錄表就是我們維護的dp矩陣，狀態(tài)轉(zhuǎn)移方程就是f(n) = max(f(n-2)+nums[n], f(n-1))。

題目2：假如有一排房子，共 n 個，每個房子可以被粉刷成紅色、藍色或者綠色這三種顏色中的一種，你需要粉刷所有的房子并且使其相鄰的兩個房子顏色不能相同。當(dāng)然，因為市場上不同顏色油漆的價格不同，所以房子粉刷成不同顏色的花費成本也是不同的。每個房子粉刷成不同顏色的花費是以一個?n x 3?的矩陣來表示的。例如，costs[0][0] 表示第 0 號房子粉刷成紅色的成本花費；costs[1][2]?表示第 1 號房子粉刷成綠色的花費，以此類推。請你計算出粉刷完所有房子最少的花費成本。

示例 1:

輸入: [[17,2,17],[16,16,5],[14,3,19]]

輸出: 10

解釋: 將 0 號房子粉刷成藍色，1 號房子粉刷成綠色，2 號房子粉刷成藍色。最少花費: 2 + 5 + 3 = 10。

答案：

分析：這道題目同樣也是動態(tài)規(guī)劃中的簡單題，在近兩年作為面試題出現(xiàn)的公司有領(lǐng)英等。雖然這道題并不是很火，難度也是簡單題，但是個人覺得對入門動態(tài)規(guī)劃還是有幫助的。一開始有的同學(xué)的思路是把每行的最小元素求和就ok了，那么這樣的狀態(tài)轉(zhuǎn)移方程就是min_cost[n] = min(costs[n][0], costs[n][1], costs[n][2]) + min_costs[n-1]。但是這種思路是錯誤的，因為對于當(dāng)前的顏色選擇，我們要知道上一次粉刷的是color，才能確定當(dāng)前狀態(tài)的color。而且我們要知道上一個狀態(tài)的三種color的各自的cost，才能確定當(dāng)前用哪個color的cost最小。什么意思呢？我舉個例子，假設(shè)costs的數(shù)組是這樣[10, 15, 30], [1, 10, 20]，然后我們理所當(dāng)然的選擇當(dāng)前行的最小元素進行求和，這樣max_value = 10+10=20（第二行不選1的原因是在第1行與第2行不能選擇同一個索引值的元素），但是其實有更便宜的選擇：15+1=16。之所以會發(fā)生這種情況是我們在選擇第二行元素的時候已經(jīng)把第一行的元素選好了，所以不要著急做出選擇。換句話說，如果先讓你選擇第二行的元素，我們是不是要針對第二行的所有元素并結(jié)合第一行的元素進行分析比較。按照這個思路，我們的狀態(tài)轉(zhuǎn)移方程應(yīng)該就是dp[i][j] = costs[i][j] + min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]), dp就是我們維護的動態(tài)規(guī)劃矩陣，其中每個元素都是選擇當(dāng)前color的最少成本。代碼實現(xiàn)可以將狀態(tài)轉(zhuǎn)移方程表達出來，但是這樣更方便讀者們的理解，而且執(zhí)行效率非常高，如圖所示：

今天的分享就做到這了，動態(tài)規(guī)劃其實還是要刷刷題的，思路形成后就會有潛意識了。希望各位讀者在評論區(qū)多提寶貴意見，多多指正，先謝謝大家了！