本文共 21100 字，大约阅读时间需要 70 分钟。
核心：状态转移方程
着力点：状态变量
思想：空间换时间，空间优化使用滚动变量
一些例子和实现代码
动态规划问题大部分属于数组内容
1.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
答：动态规划算法
假设数组的长度是 n，下标从 0到 n−1。我们用 f(i)代表以第 i个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：
因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。对于每一个f(i)实际上取决于 f(i-1)+nums[i] 和 nums[i] 的大小，那么得到动态规划的状态转移方程：f(i) = max( f(i-1)+nums[i], nums[i] )
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) if n<2: return nums[0] f=[nums[0]] for i in range(1,n): f.append(max(f[i-1]+nums[i],nums[i])) print(f) return max(f)
2.买卖股票问题
（1）一次交易
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
答：我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。形式上，对于每组 i 和 j ，其中 j>i ,我们需要找出 max(prices[j]-prices[i])。
# 我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。class Solution: def maxProfit(self, prices: List[int]) -> int: inf = int(1e9) minprice = inf maxprofit = 0 for price in prices: maxprofit = max(price - minprice, maxprofit) minprice = min(price, minprice) return maxprofit
动态规划：
题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划 的方法来解决。
当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中。
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的状态下的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的状态下的最大利润（i 从 0 开始）。
确定状态转移方程：
dp[i][0] 的转移方程，表示这一天交易完后手里没有股票。可能的转移状态为前一天已经没有股票，即 dp[i−1][0] ；或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：dp[i][0] = max（dp[i−1][0]，dp[i−1][1]+prices[i]）
dp[i][1] 的转移方程，表示这一天交易完后手里有股票。可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1] ；或者前一天结束的时候手里没有股票，即 dp[i−1][0]，这时候我们要将其买入（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。因此为了收益最大化，我们列出如下的转移方程：dp[i][1] = max（dp[i−1][1]，-prices[i]）
对于初始状态，根据状态定义我们可以知道第 0天交易结束的时候 dp[0][0] = 0，dp[0][1] = −prices[0]。
因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的，最后的答案即为 dp[n−1][0]。
class Solution: def maxProfit(self, prices: List[int]) -> int: L = len(prices) if L<2: return 0 dp0 = [None]*L dp1 = [None]*L dp0[0] = 0 dp1[0] = -prices[0] for i in range(1,L): dp0[i] = max(dp0[i-1],dp1[i-1]+prices[i]) dp1[i] = max(dp1[i-1],-prices[i]) return dp0[L-1]""" 优化：由于当前行只参考上一行，每一行就 2 个值，因此可以考虑使用「滚动变量」"""class Solution: def maxProfit(self, prices: List[int]) -> int: L = len(prices) if L<2: return 0 dp0 = 0 dp1 = -prices[0] for i in range(1,L): dp0, dp1 = max(dp0,dp1+prices[i]), max(dp1,-prices[i]) return dp0
（2）多次买卖，不限交易次数
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
答：动态规划
「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的状态下的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的状态下的最大利润（i 从 0 开始）。
确定状态转移方程：
dp[i][0] 的转移方程，表示这一天交易完后手里没有股票。可能的转移状态为前一天已经没有股票，即 dp[i−1][0] ；或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：dp[i][0] = max（dp[i−1][0]，dp[i−1][1]+prices[i]）
dp[i][1] 的转移方程，表示这一天交易完后手里有股票。可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1] ；或者前一天结束的时候手里没有股票，即 dp[i−1][0]，这时候我们要将其买入，并减少 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：dp[i][1] = max（dp[i−1][1]，dp[i−1][0]-prices[i]）
对于初始状态，根据状态定义我们可以知道第 0天交易结束的时候 dp[0][0] = 0，dp[0][1] = −prices[0]。
因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的，最后的答案即为 dp[n−1][0]。
class Solution: def maxProfit(self, prices: List[int]) -> int: L = len(prices) dp0 = [None]*L dp1 = [None]*L dp0[0] = 0 dp1[0] = -prices[0] for i in range(1,L): dp0[i] = max(dp0[i-1],dp1[i-1]+prices[i]) dp1[i] = max(dp1[i-1],dp0[i-1]-prices[i]) return dp0[L-1]""" 优化：由于当前行只参考上一行，每一行就 2 个值，因此可以考虑使用「滚动变量」 """class Solution: def maxProfit(self, prices: List[int]) -> int: L = len(prices) if L<2: return 0 dp0 = 0 dp1 = -prices[0] for i in range(1,L): dp0, dp1 = max(dp0,dp1+prices[i]), max(dp1,dp0-prices[i]) return dp0
贪心算法（针对这道题的特殊解法）
贪心算法的直觉：由于不限制交易次数，只要今天股价比昨天高，就交易。需要说明的是，贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。
由于股票的购买没有限制，因此整个问题等价于寻找 x 个不相交的区间(l_i,r_i] 使得如下的等式最大化:
""" 贪心算法，只能计算最大利润。「贪心算法」 在每一步总是做出在当前看来最好的选择。理解：（1）「最好」 的意思往往根据题目而来，可能是 「最小」，也可能是 「最大」；（2）贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的；"""class Solution: def maxProfit(self, prices: List[int]) -> int: L = len(prices) if L<2: return 0 result = 0 for i in range(1,L): result += max(prices[i]-prices[i-1],0) return result
（3）最多2笔交易
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
答：动态规划
一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过，所以一天结束会有以下状态：
第i天结束时的6种状态：
未持股，未卖出过股票：说明从未进行过买卖，利润为0 sell[i][0]
持股，未卖出过股票：可能是今天买的，也可能是之前买的（昨天也持股）.买交易一次，buy[i][1] 未持股，卖出过1次股票：可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过），卖交易一次，sell[i][1] 持股，卖出过1次股票：可能是今天买的，也可能是之前买的（昨天也持股），买交易两次，buy[i][2] 未持股，卖出过2次股票:可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过），卖交易2次，sell[i][2] 持股，卖出过2次股票：最多交易2次，这种情况不存在 买交易三次，buy[i][3]由于第一个状态的利润显然为 0，因此我们可以不用将其记录，最后一个状态是不存在的。对于剩下的四个状态，我们分别将它们的最大利润记为 buy [ i ] [1]，sell[ i ][1]，buy[ i ][ 2 ] 以及 sell[ i ][ 2 ]
一般性分析：buy[i][j] 表示第 i 天结束的时候是持股状态，并且并且进行了第 j 次交易（这里是买）。sell[i][j] 表示第 i 天结束的时候是未持股状态，并且进行了第 j 次交易（这里是卖）。
对于 buy[i][j] ，其中 j = {0，1}，我们考虑当前手上持有的股票是否是在第 i 天结束的时候买入的，j 表示当前持股的次数。如果是第 i 天买入的，那么在第 i−1 天时，我们手上不持有股票，对应状态 sell[i−1][j-1]，并且需要扣除 prices[i]的买入花费；如果不是第 i 天买入的，那么在第 i−1 天时，我们手上持有股票，对应状态 buy[i−1][j]。那么我们可以得到状态转移方程：buy[i][j]=max{ buy[i−1][j], sell[i−1][j-1]−price[i] }
同理对于 sell[i][j] ，其中 j = {0，1}，如果是第 i 天卖出的，那么在第 i−1 天时，我们手上持有股票，对应状态 buy[i−1][j]，并且需要增加 prices[i]的卖出收益；如果不是第 i 天卖出的，那么在第 i−1 天时，我们手上不持有股票，对应状态 sell[i−1][j]。那么我们可以得到状态转移方程：sell[i][j]=max{ sell[i−1][j], buy[i−1][j]+price[i] }
初始状态：根据状态定义我们可以知道第 0天交易结束的时候sell[0][0] = buy[0][0]= 0，buy[0][1] = −prices[0]。sell[0][1]= sell[0][2] = buy[0][2]float("-inf")表示不合理。并且buy[0,...,n-1][0]=sell[0,...,n-1][0] = 0即没有进行任何交易最大利润都是0.
需要注意的是，本题中 k 的最大值可以达到 10^9，然而这是毫无意义的，因为 n 天最多只能进行 ⌊n/2⌋ 笔交易，其中 ⌊x⌋= 表示对 x 向下取整。因此我们可以将 k 对 ⌊ n/2 ⌋ 取较小值之后再进行动态规划。
由于在所有的 n 天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组 prices 单调递减，我们不进行任何交易才是最优的），因此最终的答案即为 sell[n−1]列表中的最大值。
class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) if n <2: return 0 # 表示2次交易 k = 2 # 实际上对于给定的天数，最多也就n//2笔交易，所以实际的交易次数也应该在该限制之下 k = min(n//2,k) # 每一天都有可能的k+1种状态：0,...,k表示没有交易，交易一次，...交易k次.所有值的默认初始状态是0 buy = [[0]*(k+1) for i in range(n)] sell = [[0]*(k+1) for i in range(n)] # 不合理的初始状态全部赋值为负无穷大 for i in range(1,k+1): sell[0][i] = float("-inf") if i>1: buy[0][i] = float("-inf") # 初始状态 buy[0][1] = -prices[0] for i in range(1,n): for j in range(1,k+1): buy[i][j] = max( buy[i-1][j], sell[i-1][j-1]-prices[i]) sell[i][j] = max(sell[i-1][j],buy[i-1][j]+prices[i]) return max(sell[n-1]) （4）最多k笔交易
答：动态规划，分析思路和上题一模一样,只是k可能为0，则结果返回0.再加一个判定。
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) # 如果构成完成交易的天数，或者交易次数为0 if n <2 or k<1: return 0 # 实际上对于给定的天数，最多也就n//2笔交易，所以实际的交易次数也应该在该限制之下 k = min(n//2,k) # 每一天都有可能的k+1种状态：0,...,k表示没有交易，交易一次，...交易k次.所有值的默认初始状态是0 buy = [[0]*(k+1) for _ in range(n)] sell = [[0]*(k+1) for _ in range(n)] # 不合理的初始状态全部赋值为负无穷大 for i in range(1,k+1): sell[0][i] = float("-inf") if i>1: buy[0][i] = float("-inf") # 初始状态 buy[0][1] = -prices[0] for i in range(1,n): for j in range(1,k+1): buy[i][j] = max( buy[i-1][j], sell[i-1][j-1]-prices[i]) sell[i][j] = max(sell[i-1][j],buy[i-1][j]+prices[i]) return max(sell[n-1]) （5）最佳买卖股票时机含冷冻期，不限交易次数
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
答：动态规划，分析思路和无限次交易的思路一样。不同点在于状态会多一种。
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票并且不是冷冻期状态下的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的状态下的最大利润（i 从 0 开始），dp[i][2]表示第i天交易完属于冷冻期的状态下的最大利润。
确定状态转移方程：
dp[i][0] 的转移方程，表示这一天交易完后手里没有股票并且不是冷冻期。只可能是没有交易，因为如果卖就变成了冷冻期状态。可能的转移状态为前一天是冷冻期，今天依旧没持有股票并且已经解冻，即dp[i−1][2] ；或者前一天依旧是没有交易的未持股状态，即 dp[i−1][0]，这时候我们要将其卖出，并获得 prices[i] 的收益。因此为了收益最大化，我们列出如下的转移方程：dp[i][0] = max（dp[i−1][2]，dp[i−1][0]）
dp[i][1] 的转移方程，表示这一天交易完后手里有股票。可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1] ；或者前一天结束的时候手里没有股票，则一定是正常的未持有股票的状态，不然这一天不能交易，这时候我们要将其买入，并减少 prices[i] 的收益，即 dp[i-1][0]-prices[i] 。因此为了收益最大化，我们列出如下的转移方程：dp[i][1] = max（dp[i−1][1]，dp[i−1][0]-prices[i]）
dp[i][2] 的转移方程，表示这一天j结束处于冷冻期。则这一天一定进行了交易，即 dp[i-1][1]+prices[i] 。因此列出转移方程：dp[i][2] = dp[i−1][1]+prices[i]
对于初始状态，根据状态定义我们可以知道第 0天交易结束的时候 dp[0][0] = dp[0][2]= 0，dp[0][1] = −prices[0].
因此，我们只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n-1][0] 和 dp[n-1][2] 的收益必然是大于 dp[n-1][1] 的，最后的答案即为 max( dp[n−1][0], dp[n-1][2] )。
class Solution: def maxProfit(self, prices: List[int]) -> int: # prices = [1,4,2] n = len(prices) if n<2: return 0 # 第i天结束的状态：没有持有股票（不是冷冻期），持有股票，冷冻期没有股票 dp0,dp1,dp2 = [0]*n,[0]*n,[0]*n dp1[0] = -prices[0] for i in range(1,n): dp0[i] = max(dp0[i-1],dp2[i-1]) dp1[i] = max(dp1[i-1],dp0[i-1]-prices[i]) dp2[i] = dp1[i-1]+prices[i] return max(dp0[n-1],dp2[n-1])""" 优化：由于当前行只参考上一行，每一行就 2 个值，因此可以考虑使用「滚动变量」 """class Solution: def maxProfit(self, prices: List[int]) -> int: # prices = [1,4,2] n = len(prices) if n<2: return 0 # 第i天结束的状态：没有持有股票（不是冷冻期），持有股票，冷冻期没有股票,分别设置为滚动变量，并且初始化 dp0,dp1,dp2 = 0, -prices[0], 0 for i in range(1,n): # 注意如果不使用中间变量，不能分开写，因为右边的全是前一天的状态，左边的全是今天结束的状态。 dp0,dp1,dp2 = max(dp0,dp2), max(dp1,dp0-prices[i]), dp1+prices[i] return max(dp0,dp2)
3.爬楼梯
| 简单跳台阶 |
| 变态跳台阶 |
| 三步问题 |
| 最少体力爬楼梯 |
（1）简单跳台阶。
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
答：动态规划
青蛙每次只有一阶或者两阶两种跳法，假设跳n级台阶的方法总共 f(n) ，那么
假设第一次跳的是一阶，那么剩下n-阶，跳法是 f(n-1)
假设第一次跳的是二阶，那么剩下n-2阶，跳法是 f(n-2)初始状态，f(1) = 1，f(2) = 2
状态转移方程：f(n) = f(n-1)+f(n-2) 斐波那契数列
class Solution: def climbStairs(self, n: int) -> int: if n<1: return elif n==1: return 1 elif n==2: return 2 else: base = int(1e9+7) f = [0]*n # 第0阶一直到第n-1阶实际上就是1级和n级 f[0],f[1]=1,2 for i in range(2,n): f[i] = (f[i-1]+f[i-2])%base return f[n-1]""" 优化，因为总是使用f[i-1]和f[i-2], 使用滚动变量 """class Solution: def climbStairs(self, n: int) -> int: if n<1: return elif n==1: return 1 elif n==2: return 2 else: base = int(1e9+7) f = 0 #我们求的最后结果 f1,f2=1,2 # 一阶和二阶的对应方法数目 for i in range(2,n): f = (f1+f2)%base # 更新，滚动 f1 = f2 # 更新，滚动 f2 = f ## 更新，滚动 return f
（2）变态跳台阶
一个台阶总共有n级，如果一次可以跳1级，也可以跳2级......它也可以跳上n级。此时该青蛙跳上一个n级的台阶总共有多少种跳法？注意：给定 n 是一个正整数。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
答：动态规划，因为一次性可以跳1，2，...，n总共n种方式，则
假设第一次跳的是一阶，那么剩下n-阶，跳法是 f(n-1)
假设第一次跳的是二阶，那么剩下n-2阶，跳法是 f(n-2) ...... 假设第一次跳的是n-1阶，那么剩下1阶，跳法是 f(1) 假设第一次跳的是n阶，那么剩下0阶，跳法是 f(0)那么，f(n) = f(n-1)+f(n-2)+...+f(0)，又可知有f(n-1) = f(n-2)+f(n-3)+...+f(0)
两式整理得到状态转移方程：f(n) = 2*f(n-1)
初始状态：f(0) = 0不存在，f(1) = 1
class Solution: def climbStairs(self, n: int) -> int: if n<1: return elif n==1: return 1 else: f = [0]*n # 第0阶一直到第n-1阶实际上就是1级和n级 f[0]=1 base = int(1e9+_7) for i in range(2,n): f[i] = 2*f[i-1]%base return f[n-1]""" 优化，因为总是使用f[i-1], 使用滚动变量 """class Solution: def climbStairs(self, n: int) -> int: if n<1: return elif n==1: return 1 else: f = 0 #我们求的最后结果 f1 = 1 # 一阶的对应方法数目 base = int(1e9+_7) for i in range(2,n): f = 2*f1%base # 更新，滚动 f1 = f # 更新，滚动 return f
（3）三步问题
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
答：动态规划，因为一次性可以跳1，2，3 总共3种方式，则
假设第一次跳的是一阶，那么剩下n-阶，跳法是 f(n-1)
假设第一次跳的是二阶，那么剩下n-2阶，跳法是 f(n-2) 假设第一次跳的是三阶，那么剩下n-3阶，跳法是 f(n-3)得到状态转移方程：f(n) = f(n-1)+f(n-2)+f(n-3)
初始状态：f(0) = 0不存在，f(1) = 1，f(2)=2，f(3)=4
class Solution: def waysToStep(self, n: int) -> int: if n<1: return elif n==1: return 1 elif n==2: return 2 elif n==3: return 4 else: f = [0]*n base=int(1e9+7) f[0],f[1],f[2] = 1,2,4 for i in range(3,n): f[i] = (f[i-1]+f[i-2]+f[i-3])%base return f[n-1] """ 优化，使用滚动变量 """class Solution: def waysToStep(self, n: int) -> int: if n<1: return elif n==1: return 1 elif n==2: return 2 elif n==3: return 4 else: f = 0 base=int(1e9+7) f1,f2,f3 = 1,2,4 for i in range(3,n): f = (f1+f2+f3)%base f1 = f2 f2 = f3 f3 = f return f
（4）最少体力爬楼梯
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
例子1：
输入：cost = [10, 15, 20]输出：15解释：
体力值 10 15 20 水平线 0阶 1阶 2阶 天台一次最多可以跨两步。cost[i]为离开当前台阶需要的体力，水平线出发不花体力。如果离开水平线跨1步到了0阶，耗费体力为0；然后离开0阶跨一步或两步都是10体力，如果跨到2阶，这时还没到天台，还要跨一步离开2阶要20体力。所以共需要30体力。如果一开始跨2步直接到1阶，花费0体力，然后离开1阶跨两步直接上天台，花费15体力。所以共需要15体力
例子2：输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]输出：6解释：最低花费方式是从 水平线花费体力0跨一步到达0阶，然后花费体力1离开跨两步到2阶，接着花费体力1从2阶跨两步到4阶，花费体力1离开4阶跨2步到6阶，接着花费体力1从6阶跨1步到7阶，然后花费2体力从7阶跨两步到9阶，最后花费1体力离开9阶到达楼顶。因此一共花费 6 。
答：动态规划
假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n−1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
设置状态变量 dp[i] , 表示到达第n阶的最小花费。因为花费体力之后可以跨一步也可以跨两步，因此dp[i] 到达第i阶，可能是从dp[i-1]跨一步到达，即 dp[i-1]+cost[i-1]；也可能是从dp[i-2]跨两步到达，即dp[i-2]+cost[i-2]，那么最小花费则从里面选择最小的方案
因此状态转移方程： dp[i] = min( dp[i-1]+cost[i-1], dp[i-2]+cost[i-2] )
初始化，离开地面，跨上第0阶和第1阶不需要花费体力，即dp[0]=dp[1]=0
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) if n<2: return 0 dp = [0]*(n+1) # n+1表示包含了楼顶，需要到达楼顶，即求dp[n]的体力花费值；并且dp[0]和dp[1]已经初始化为0 for i in range(2,n+1): dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) return dp[n]""" 优化, 使用滚动变量 """class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) if n<2: return 0 dp = 0 dp1 = 0 dp2 = 0 for i in range(2,n+1): dp = min(dp1+cost[i-1], dp2+cost[i-2]) dp2 = dp1 dp1 = dp return dp
4.打家劫舍和房子
| 打家劫舍 |
| 打家劫舍Ⅱ |
| 打家劫舍Ⅲ |
| 栅栏涂色 |
| 粉刷房子 |
| 粉刷房子Ⅱ |
| 粉刷房子Ⅲ |
（1）打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
答：动态规划
状态变量：dp[i]表示前 i+1 间房偷窃的最高金额，那么可能是前 i-1 间房的总额再加上第i间房，即dp[i-2]+nums[i]，或者是前i间房偷窃金额，即dp[i-1]，取最大值。
状态转移方程： dp[i] = max( dp[i-2]+nums[i], dp[i-1] )
初始值：dp[0] = nums[0]，dp[2] = max( nums[0],nums[1] )
class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n<1: return if n==1: return nums[0] if n==2: return nums[1] f = [0]*(n) f[0],f[1] = nums[0],max(nums[0],nums[1]) for i in range(2,n): f[i] = max(f[i-2]+nums[i],f[i-1]) return f[n]""" 优化，可以使用滚动数组，这里不再赘述 """
（2）打家劫舍Ⅱ，房屋围成一圈
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
答：动态规划
注意：第一个房屋和最后一个房屋是紧挨着的，当有3个和以上的时候，会首尾相连。所以两个房子不构成圈。
如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋。假设数组 nums 的长度为 n。如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0,n−2]；
如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。假设数组 nums 的长度为 n。如果偷窃最后一间房屋，则偷窃房屋的下标范围是 [1,n−1]；
因此解题和上面方法一样，不再赘述和重复。注意可以使用函数，因为变化的只是下标。
（3）打家劫舍Ⅲ，房屋是二叉树（二叉树的算法，不属于动态规划）
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
例如：
[3,2,3,null,3,null,1]
3
/ \ 2 3 \ \ 3 1输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.输入: [3,4,5,1,3,null,1]
3
/ \ 4 5 / \ \ 1 3 1输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.（4）栅栏涂色
有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。注意: n 和 k 均为非负的整数。
示例:
输入: n = 3，k = 2 输出: 6 解析: 用 c1 表示颜色 1，c2 表示颜色 2，所有可能的涂色方案有:柱 1 柱 2 柱 3
----- ----- ----- ----- 1 c1 c1 c2 2 c1 c2 c1 3 c1 c2 c2 4 c2 c1 c1 5 c2 c1 c2 6 c2 c2 c1答：动态规划
状态变量：dp[i]表达式刷到第i个栅栏的颜色总方法数，那么要求给全部栅栏上色，则转化成了求dp[n-1]
第i个栅栏的颜色，有可能和第i-1个栅栏的颜色不一样，总共k种颜料，则dp[i-1]*(k-1)；或者有可能和第i-1个栅栏的颜色一样，则和第i-2个栅栏不一样，则dp[i-2]*(k-1)。因此总共是这两种情况的和。
状态转移方程： dp[i] = dp[i-1]*(k-1)+dp[i-2]*(k-2)
初始值：dp[0] = k, dp[2] =k*k
def coloringFence（n:int,k:int): if n == 0 or k ==0: return 0 if n==1: return k if n==2: return k**2 dp = [0]*n dp[0],dp[1] = k,k**2 for i in range(2,n): dp[i] = dp[i-1]*(k-1)+dp[i-2]*(k-1) return dp[n-1]""" 优化，使用滚动变量 """def coloringFence（n:int,k:int): if n == 0 or k ==0: return 0 if n==1: return k if n==2: return k**2 dp = 0 dp1,dp2 = k,k**2 for i in range(2,n): dp = dp1*(k-1)+dp2*(k-1) dp2 = dp1 dp1 = dp return dp
（5）粉刷房子, 3种颜色和三种单价
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。注意：所有花费均为正整数。
分析：每一个房子有三种涂料，每种涂料在不同房子的价格不一样，要求最小花费，那么应该比较涂最后房间的哪一种颜色的花费
状态变量： dp[i][j] 表示到第i个房间涂第j种颜色的时候，总共花费，即也包含了前i-1个房间的费用。
状态转移方程：
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[0][1] = cost[0][1]，dp[0][1] = cost[0][1]，dp[0][2] = cost[0][2]
def minCost(costs:List[List[int]]): n = len(costs) if n<1: return 0 if n<2: return min(costs[0]) dp = costs for i in range(1,n): 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] return min(dp[n-1])
（6）粉刷房子Ⅱ，k种颜色k种单价
假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n*k 的矩阵来表示的。例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。注意：所有花费均为正整数。
答：和上题类似，只不过从三种颜色变成了k种颜色。
因此定义状态变量： dp[i][j] 表示房子i涂成颜色j，此时将 0-i 房子都涂完的最小花费。那么，该题的答案应该是 dp[n-1][:] 中的最小值。
状态转移方程： dp[i][j] = min(dp[i-1][c]) + cost[i][j] ，其中c != j
def minCost(costs:List[List[int]]): n = len(costs) if n<1 : return 0 k = len(costs[0]) if n<2 or k==1: return min(costs[0]) dp = [ [float("inf")]*k for _ in range(n)] dp[0] = costs[0] for i in range(1,n): for j in range(k): for c in range(k): dp[i][j] = min(dp[i][j],dp[i-1][c])+costs[i][0] return min(dp[n-1]) （7）粉刷房子Ⅲ
在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）
给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：
houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。 cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。
答：动态规划
需要
三个数据存储：当前是第几个房子、当前房子组成的街区数、当前房子的颜色
定义状态变量： dp[i][j][k] 表示前 i 个房子组成 j 个街区，且第i个房子的颜色为k，此时的最小花费数据范围：房子i in [0, m-1]，街区 j in [0,target]，颜色 k in [0, n]
状态转移：
当前房子有颜色：如果第i-1个房子和第 i 个房子颜色不同，则会形成新的街区；如果第 i-1个房子和第 i 个房子颜色相同，则街区数量不变注意因为。第i个房子有颜色，所以没有cost费用。
dp[i][j][k] = min( dp[i-1][j-1][c], dp[i-1][j][k] ) ，其中c是不和k重复的颜色，k的值是固定的等于当前房子的颜色
当前房子无颜色：如果第i-1个房子和第 i 个房子颜色不同，则会形成新的街区；如果第 i-1个房子和第 i 个房子颜色相同，则街区数量不变注意因为。第i个房子无颜色，所以有cost费用。
dp[i][j][k] = min( dp[i-1][j-1][c], dp[i-1][j][k]) + costs[k] ， 其中c是不和k重复的颜色，k不是固定的颜色
那么最后得到的最小花费：min( dp[n-1][target] )
初始值： 第一个房子没颜色，那么第一个房子的花费就是对应颜料的花费，即dp[0][1][i]=cost[i]；如果第一个房子有颜色，那么该房子没有花费，并且该房子的状态都已经确定，存在其他颜色是不合理的，不合理的设置为一个很大的数。
class Solution: def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int: if m
转载地址：http://rcwbf.baihongyu.com/