動態規劃分析問題五步曲

不清楚動態規劃分析問題是哪關鍵的五步的少年們可以移步到
鏈接: 動態規劃算法基礎
這篇文章非常詳細的介紹了動態規劃算法是如何分析和解決問題的

題目概述

鏈接: 粉刷房子

1. 狀態表示（題目要求+自己的經驗）
   本題狀態：分析第i個位置，發現第i個位置可以選擇紅色，藍色和綠色
   顯然，一個狀態表示是不夠的得分類討論
   red[i] : 表示i個位置粉刷為紅色的最小花費
   blue[i] : 表示i個位置粉刷為藍色的最小花費
   green[i] : 表示i個位置粉刷為綠色的最小花費

2. 狀態轉移方程推導
   對i位置進行分類討論，若i位置一直顏色，則其他i-1的顏色坑定為 其他兩種顏色的一種
   輕松得出狀態轉移方程
   

3. 初始化（防止越界+結合狀態表示初始化）
   根據狀態轉移方程，當i = 0時會發生越界
   根據狀態表示 :
   初始化令red = cost[0][0] , blue = cost[0][1] , green = cost[0][2];

4. 填表順序（分析要填i位置前一個依賴狀態的位置）
   本題三個dp表顯然都是從左到右填表

5. 返回值（由題目要求來）
   因此我們并不確定最終位置會染成什么顏色，又根據三個表的狀態表示
   只需要返回 三者的最小值即可

代碼編寫

有了動態規劃五步曲我們就可以寫出非常優雅的代碼了

  int minCost(vector<vector<int>>& costs) {int n = costs.size();vector<int> red(n);auto blue = red , green = red;red[0] = costs[0][0],blue[0] = costs[0][1],green[0] = costs[0][2];for(int i = 1 ; i < n ; i++){red[i] = min(blue[i-1],green[i-1]) + costs[i][0];blue[i] = min(red[i-1],green[i-1]) + costs[i][1];green[i] = min(red[i-1],blue[i-1]) + costs[i][2];}return min(red[n-1],min(blue[n-1],green[n-1]));}

少年，今天你又進步了一點點喲，明天繼續加油吧