一、粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
注意：
所有花费均为正整数。
示例：

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。最少花费: 2 + 5 + 3 = 10。

思路

1.首先根据示例容易认为只需每一行取最小值即可，而忽略了相邻两个房子的颜色必须不同
2.盲目选最小还会有一个问题如：[[4,2,3],[1111,3,2222]],如果第一行选择2，第二行就被迫放弃最小的3，而使总价格变得非常大。类似于贪心，没有考虑整体。
3.所以根据上述问题，3种颜色的情况我们都要考虑，最后在其中选出花费最小的。这时我们需要一个二维数组$dp[i][j]$，i表示粉刷第i个房子用第j个颜色所需要的花费。然后重点是状态转移方程：$dp[i][j] = min(dp[i-1][(j+1) \% 3], dp[i-1][(j+2) \% 3]) + costs[i][j]$

代码

class Solution:def minCost(self, costs: List[List[int]]) -> int:n = len(costs)if n==0: return 0k = len(costs[0])dp = [[float('inf') for _ in range(k)] for _ in range(n)]for j in range(k):dp[0][j] = costs[0][j]for i in range(1,len(costs)):for j in range(k):dp[i][j] = min(dp[i-1][(j+1) % 3], dp[i-1][(j+2) % 3]) + costs[i][j]return min(dp[n-1])

二、使用最小花费爬楼梯

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。

示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释:最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

思路

首先仔细分析可知可以由动态规划来解，因为明显地可以分解为子问题的最优解来解决。然后建立状态转移方程问题就解决了一大半了。
状态转移方程：$dp[i] = min(dp[i-1], dp[i-2]) + cost[i]$
$dp[]$用来记录每到一个阶梯所需要的最小代价
显然$dp[0] = cost[0],dp[1] = cost[1]$。

代码

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:size = len(cost)dp = [0 for _ in range(size)]dp[0] = cost[0]dp[1] = cost[1]for i in range(2, size):dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]return min(dp[-1], dp[-2])

总结

看了这么多关于动态规划的，感觉和递归有相似之处，与之不同的是动态规划记录每一步的结果，之后能够重复利用这个结果，所以效率会高一点。在做这两题当中也让我意识到子问题以及它的状态转移方程的重要性，状态转移方程在我看来就和递推公式差不多，找到子问题间的关系。有了这些感悟，希望能够顺利做出接下来的题目。