# 动态规划
# 思想
感觉很像高中数列的思想，给出首项，以及一个递推公式，让你求任一项的值。
# 步骤
- 寻找状态转移方程
- 建立合适的数据结构表
- 填表
# 题目
# 爬楼梯 (opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
# 思路
到达第 n 级阶梯可以从 n - 1 级走一步，或者 n - 2 级走两步，所以第 n 级有 dp[n - 1] + dp[n - 2] 种方法
# 答案
function climbStairs(n: number): number {
const dp: number[] = []
dp[0] = 0
dp[1] = 1
dp[2] = 2
for(let i = 3; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1]
}
return dp[n]
}
# 打家劫舍 (opens new window)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
# 思路
由于不可以偷盗相邻的房屋，所以第 n 间房屋可盗窃的最大值要么是第 n - 1 间房屋可盗窃的最大值，要么是第 n - 2 个房屋可盗窃的最大值加上当前房屋可盗窃的价值，即 dp[n] = Number.max(dp[n - 1], dp[n - 2] + n)
# 答案
function rob(nums: number[]): number {
const n = nums.length
if(!n) return 0
if(n === 1) return nums[0]
const dp: number[] = []
dp[0] = nums[0]
dp[1] = Number.max(nums[0], nums[1]) // 第二间可盗窃的最大值要么是他自己，要么是他上一间房，符合动态公式
for(let i = 2; i < n; i++) {
dp[i] = Number.max(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[n - 1]
}
# 最大正方形 (opens new window)
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积
# 思路
题目要求最大正方形的面积，所以需要找出最大正方形的边长。
在矩阵中找最大正方形，矩阵中只有 0｜1，全部为 1 才是正方形。
如何知道哪里是 0，哪里是 1，需要穷举，但不需要全部列出，即为动态规划。
动态规划第一步，先假设我们创建了一个二维数组 dp，用来存储 这个点为右下角的最大正方形的边长。
下面开始找状态转换方程
思路：
假设有矩阵如下
/**
* 1 0 1 1 1
* 1 1 1 1 1
* 1 1 1 1 1
* 1 0 0 1 1
*/
我们随便找一个点，例如最右下角的点，设该点最大正方形的边长为 dp[i][j]，我们用估算一下 dp[i][j] === 2，为什么呢？
因为我们看到 dp[i - 1][j]、dp[i - 1][j - 1]、dp[i][j - 1] 这三个点都是 1，又因为 dp[i - 2][j] 是 0，所以 dp[i][j] === 2。
也就是说，我们不单只是看这三个相邻点，还要看 这三个相邻点为正方形右下角的边长情况，找出它们中的最小值即为 dp[i][j] 的值，也就是这个点的最长变长。
转换公式为：
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
# 答案
function maximalSquare(matrix: string[][]): number {
const rows = matrix.length;
if (!rows) return 0;
const cols = matrix[0].length;
const dp: number[][] = [];
let max = 0;
for (let i = 0; i < rows + 1; i++) {
if (i === 0) {
dp[i] = Array(cols + 1).fill(0);
} else {
dp[i] = [0];
}
}
for (let i = 1; i < rows + 1; i++) {
for (let j = 1; j < cols + 1; j++) {
if (matrix[i - 1][j - 1] === "1") {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
max = Math.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max * max;
}
# 零钱兑换 (opens new window)
给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1.
# 思路
假设组成金额 S 所需要的最少硬币数量为 F(S)，那么假设最后一枚硬币的面值是 C，那么得到转移方程：
F(S) = F(S - C) + 1
但是我们不知道最后一枚硬币的面值是多少，所以我们需要穷举每个硬币面值，并选择其中的最小值。
# 答案
function coinChange(coins: number[], amount: number): number {
const dp = new Array(amount + 1).fill(Infinity)
dp[0] = 0 // 当金额为0时，不需要硬币
for(const coin of coins) {
for(let i = 1; i <= amount; i++) {
if(i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
}
# 不同路径 (opens new window)
一个机器人位于一个 m * n 网格的左上角（其实点在下图中标记为“Start”）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径。
# 思路
我们假设 dp[i][j] 就是到达 i，j 最多路径。
因为机器人每次只能向下或者向右移动一步，所以得到动态方程：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
对于第一行 dp[0][j]或者第一列 dp[i][0] ，由于都是在边界，所以只能是 1
# 答案
// 第一版 时间复杂度 O(m * n)
function uniquePaths(m: number, n: number): number {
if( m === 1 && n === 1) return 1
const dp: number[][] = []
const rows: number[] = [0]
for(let i = 0; i < n - 1; i++) {
rows.push(1)
}
dp.push(rows)
for(let i = 0; i < m - 1; i++) {
dp.push([1])
}
for(let i = 1; i < m; i++){
for(let j = 1; j < n; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
# 股票状态机
6 道股票题都有共性，我们通过对第四题（限制最大交易次数为 k）的分析一道一道解决。因为第四题是一个最泛化的形式，其他的问题都是这个形式的简化。
第一题只能进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = infinity；第三题是只进行 2 次交易，相当于 k = 2；剩下两道题也是不限次数，但是加了交易【冷冻期】和【手续费】的额外条件，其实也就是第二题的变种。
# 穷举框架
首先还是一样的思路，如何穷举？
递归其实符合我们思考的逻辑，一步步推进，遇到无法解决的就丢给递归，一不小心就做出来了，可读性还很好。缺点就是一旦出错，你很难找到错误出现的原因。
在这里，我们不想用递归思想进行穷举，而是利用【状态】进行穷举。我们具体到每一天，看看总共可能有几种【状态】，再找出每个【状态】对应的【选择】。我们要穷举所有【状态】，穷举的目的是根据对应的【选择】更新状态。听起来抽象，你只要记住【状态】和【选择】两个词就行了。
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
比如说这个问题，每天都有三种【选择】：买入、 卖出、无操作，我们用 buy、sell、rest 表示这三种情况。但问题是，并不是每天都可以任意选择这三种状态，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分成两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提操作。
很复杂对吧，不要怕，我们现在的目的只是穷举，你有再多的状态，老夫要做的就是一把梭全部列举出来。这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：
dp[i][k][0 or 1]
0 <= i <= n-1, 1 <= k <= K
n 为天数，大 K 为最多交易数
此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
而且我们可以用自然语言描述出每一个状态的含义，比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。读者可能问为什么不是 dp[n - 1][K][1]？因为 [1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者。
记住如何解释「状态」，一旦你觉得哪里不好理解，把它翻译成自然语言就容易理解了。
# 状态转移框架
现在，我们完成了「状态」的穷举，我们开始思考每种「状态」有哪些「选择」，应该如何更新「状态」。只看「持有状态」，可以画个状态转移图。
通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
max( 选择 rest , 选择 sell )
// 解释：今天我没有持有股票，有两种可能：
// 要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
// 要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
max( 选择 rest , 选择 buy )
// 解释：今天我持有着股票，有两种可能：
// 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
// 要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
# 买卖股票的最佳时机 (opens new window)
给定一个数组，如果第 i 个元素是股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
function maxProfit(prices: number[]): number {
const n = prices.length
if(!n) return 0
let min = prices[0]
const dp: number[] = [0]
for(let i = 1; i <= n; i++) {
min = Math.min(prices[i], min)
dp[i] = Math.max(dp[i - 1], prices[i] - min)
}
return dp[n - 1]
}
# 买卖股票的最佳时机II (opens new window)
给定一个数组，如果第 i 个元素是股票的第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
# 思路
- 只要股票上涨，上涨的部分就是我的利润，可以理解为上涨期间第一天买入，然后持有到上涨最后一天卖出
- 只要股票价格下跌，那么在下跌前一天卖出，并且下跌期间不买入
# 答案
function maxProfit(prices: number[]): number {
let profit = 0
for(let i = 0; i < prices.length - 1; i++) {
if(prices[i + 1] > prices[i]) {
profit += prices[i + 1] - prices[i]
}
}
return profit
}