粉刷房子（简单多状态dp问题）

问题描述与解题思路

粉刷房子
这个题只要你搞清楚dp[i][j]的含义，后面的状态转移方程也很好求，然后代码也很好写。

确定本题的状态表示

dp[i][0] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上红色，此时的最小花费
dp[i][1] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上蓝色，此时的最小花费
dp[i][2] 表示：粉刷到 i 位置的时候，最后一个位置粉刷上绿色，此时的最小花费

确定本题的状态转移方程

dp[i][0] =min( dp[i-1][1],dp[i-1][2])+costs[i][0]
dp[i][1] =min( dp[i-1][0],dp[i-1][2])+costs[i][1]
dp[i][2] =min( dp[i-1][0],dp[i-1][1])+costs[i][2]

填表求值

根据初始条件和状态转移方程，确定填表顺序，进而逐步填满dp表，最终返回题目要的结果

代码实现

class Solution {
public:int minCost(vector<vector<int>>& costs) {int m=costs.size();vector<vector<int>> dp(m+1,vector<int>(3,0));for(int i=1;i<=m;i++){dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i-1][2];}return min({dp[m][0],dp[m][1],dp[m][2]});}
};