力扣面试经典 150 题 - DP 状态转移方程速查 • IcyDesert's blog

作速查表用。仅提供思路，而没有涉及空间压缩等技巧。另外可以点击下方 Hide Answers 来隐藏答案。

一维动态规划

爬楼梯

假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。每次你可以爬 $1$ 或 $2$ 个台阶。你有多少种不同的方法可以爬到楼顶呢？

$dp[i]$ 表示爬到第 $i$ 阶楼梯的方法数。

$dp[i] = dp[i-1] + dp[i-2]$

$dp[1] = 1, dp[1] = 2$

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 $nums$ ，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

$dp[i]$ 表示前 $i$ 间房屋能偷窃到的最高金额。

$dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$

$dp[0]=nums[0], dp[1] = \max(nums[0], nums[1])$

单词拆分

给你一个字符串 $s$ 和一个字符串列表 $wordDict$ 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 $s$ 则返回 $true$ 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

$dp[i]$ 表示字符串 $s$ 的前 $i$ 个字符能否被空格拆分为若干个字典中出现的单词。

$dp[i] = dp[j] \: \&\& \: (s[j, i-1] \in wordDict)$ ，其中 $0 \le j < i$

$dp[0] = true$

零钱兑换

给你一个整数数组 $coins$ ，表示不同面额的硬币；以及一个整数 $amount$ ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

$dp[i]$ 表示凑成金额 $i$ 所需的最少硬币个数。

$dp[i] = \min(dp[i - coin] + 1)$ ， $coin$ 为遍历 $coins$ 的变量

$dp[0] = 0; dp[i] = -1 ,i < 0$

最长递增子序列

给你一个整数数组 $nums$ ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

$dp[i]$ 表示以 $nums[i]$ 结尾的最长递增子序列的长度。

$dp[i] = \max(dp[j]) + 1$ ，其中 $0 \le j < i$ 且 $nums[j] < nums[i]$

$dp[0] = 1$

多维动态规划

三角形最小路径和

给定一个三角形 $triangle$ ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标+1 的两个结点。也就是说，如果正位于当前行的下标 $i$ ，那么下一步可以移动到下一行的下标 $i$ 或 $i + 1$ 。

$dp[i][j]$ 表示到达第 $i$ 行第 $j$ 列元素的最小路径和。

$dp[i][j] = \min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]$

$dp[0][0] = triangle[0][0]$

最小路径和

给定一个包含非负整数的 $m \times n$ 网格 $grid$ ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

$dp[i][j]$ 表示到达网格 $(i, j)$ 的最小路径和。

$dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$

$dp[0][0] = grid[0][0]$

不同路径 II

给定一个 $m \times n$ 的整数数组 $obstacleGrid$ 。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 $grid[m - 1][n - 1]$ ）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 $1$ 和 $0$ 来表示。机器人的移动路径中不能包含任何有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

$dp[i][j]$ 表示到达网格 $(i, j)$ 的路径数量。

若 $obstacleGrid[i][j] == 1$ ，则 $dp[i][j] = 0$ 。否则 $dp[i][j] = dp[i-1][j] + dp[i][j-1]$

最长回文子串

给你一个字符串 $s$ ，找到 $s$ 中最长的回文子串。如果字符串向前和向后读都相同，则它满足回文性。子字符串是字符串中连续的非空字符序列。

$dp[i][j]$ 表示字符串 $s$ 从索引 $i$ 到 $j$ 的子串是否为回文串。

$dp[i][j] = (s[i] == s[j]) \:\&\&\: (j - i < 3 \:||\: dp[i+1][j-1])$

$dp[i][i] = true$

交错字符串

给定三个字符串 $s1, s2, s3$ , 验证 $s3$ 是否是由 $s1$ 和 $s2$ 交错组成的。（略去又长又臭的精细的交错定义）

$dp[i][j]$ 表示 $s1$ 的前 $i$ 个字符和 $s2$ 的前 $j$ 个字符能否交错组成 $s3$ 的前 $i+j$ 个字符。

\begin{aligned} dp[i][j] &= (dp[i-1][j] \:\&\&\: s1[i-1] == s3[i+j-1]) \:||\: \\ & (dp[i][j-1] \:\&\&\: s2[j-1] == s3[i+j-1]) \end{aligned}

$dp[0][0] = true$

编辑距离

给你两个单词 $word1$ 和 $word2$ ，请返回将 $word1$ 转换成 $word2$ 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

$dp[i][j]$ 表示 $word1$ 的前 $i$ 个字符和 $word2$ 的前 $j$ 个字符之间的编辑距离。

若 $word1[i-1] == word2[j-1]$ 则 $dp[i][j] = dp[i-1][j-1]$

否则 $dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])$

$dp[0][j] = j, dp[i][0] = i$

买卖股票的最佳时机 III

给定一个数组，它的第 $i$ 个元素是一支给定的股票在第 $i$ 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

定义四个状态：

$buy1$ : 第一次买入后的最大收益
$sell1$ : 第一次卖出后的最大收益
$buy2$ : 第二次买入后的最大收益
$sell2$ : 第二次卖出后的最大收益

$buy1 = \max(buy1, -prices[i])$ $sell1 = \max(sell1, buy1 + prices[i])$ $buy2 = \max(buy2, sell1 - prices[i])$ $sell2 = \max(sell2, buy2 + prices[i])$

买卖股票的最佳时机 IV

给定一个整数数组 $prices$ ，它的第 $i$ 个元素 $prices[i]$ 是一支给定的股票在第 $i$ 天的价格，和一个整数 $k$ 。设计一个算法来计算你所能获取的最大利润。你最多可以完成 $k$ 笔交易。

$dp[i][j][0]$ : 第 $i$ 天，第 $j$ 次交易，手里没有股票的最大收益

$dp[i][j][1]$ : 第 $i$ 天，第 $j$ 次交易，手里有股票的最大收益

$dp[i][j][0] = \max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])$

$dp[i][j][1] = \max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])$

$dp[0][j][0] = 0$ $dp[0][j][1] = -prices[0]$

最大正方形

在一个由 $'0'$ 和 $'1'$ 组成的二维矩阵内，找到只包含 $'1'$ 的最大正方形，并返回其面积。

$dp[i][j]$ 表示以 $(i, j)$ 为右下角的最大正方形的边长。

若 $matrix[i-1][j-1] == '1'$ ，则：

$dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])$

否则 $dp[i][j] = 0$