动态规划学习

动态规划学习

本文持续更新

1、基础

特性

能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

例如：面值为1，5，10，使用最少数量钞票凑出面值15。

• 无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题f(15)没有影响。
• 最优子结构：大问题的最优解可以由小问题的最优解推出。利用w=14,10,4的最优解，我们即可算出w=15的最优解。

求解步骤

1. 确定dp数组（dp table）以及下标的含义（设计状态）
2. 确定递推公式（确定状态转移方程）
3. dp数组如何初始化（确定初始状态）—— 不同路径
4. 确定遍历顺序（执行状态转移）—— 背包问题
5. 举例推导dp数组（计算最终解）

判断动规依据

• 将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
• 有限状态自动机，有向无环图，有起始和终止节点，每一个节点代表一个状态，任何一个非起始节点都可以从其他节点转移过来（状态转移），空间换时间，通过初始状态计算出终止状态。
• 将节点抽象，关系用边排序，拓扑排序无环，则可能是动态规划，不是动态规划可能需要暴力搜索或贪心求解。并且如果状态数乘以状态转移小于10的6次方通常可以动态规划求解。

资料

=oBt53YbR9Kk
/
/
/@al.eks/the-ultimate-guide-to-dynamic-programming-65865ef7ec5b

2、题目

/

.Dynamic-Programming/01.Dynamic-Programming-Basic/01.Dynamic-Programming-Basic/

LCR 126. 斐波那契数

求解步骤

• 1 确定dp数组含义：dp[i] 第i个斐波那契数
• 2 递推公式：dp[i] = dp[i - 1] + dp[i - 2]
• 3 dp数组初始化：dp[0] = 0 dp[1] = 1
• 4 遍历顺序：从前面的数得到后面的结果，从前向后遍历
• 5 打印dp数组

题解

var fib = function(n) {// 1状态 dp[n]表示n的的斐波那契数const dp = new Array(n);// 2初始化dp[0] = 0, dp[1] = 1;// 3状态转移方程 dp[n] = dp[n - 1] + dp[n - 2]// 4执行for (let i = 2; i <= n; i++) {// 答案要求取模 (x+y)⊙p=(x⊙p+y⊙p)⊙p ⊙取模dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;}// 状态压缩：求解n只需要n - 1 和 n - 1的斐波那契数，所以可以优化dp数组，维持长度为3数组，不断更新前面两个值/*for (let i = 2; i <= n; i++) {dp[2] = (dp[1] + dp[0]) % 1000000007;dp[0] = dp[1];dp[1] = dp[2];}*/// 5返回结果return dp[n];
};

复杂度

• 时间：O(N)
• 空间：O(1)

LCR 127. 跳跃训练

求解步骤

可以转换成 LCR 126. 斐波那契数

• 1 确定dp数组含义：dp[i] 到达第i层的方法
• 2 递推公式：dp[i] = dp[i - 1] + dp[i - 2]
• 3 dp数组初始化：dp[1] = 1 dp[2] = 2
• 4 遍历顺序：从前面的数得到后面的结果，从前向后遍历
• 5 打印dp数组
  
  题解

var trainWays = function(num) {if (num < 2) {return 1;}const dp = new Array(3);// 初始值和斐波那契数不一样dp[0] = 1不是0dp[0] = 1; dp[1] = 1;for (let i = 2; i <= num; i++) {dp[2] = (dp[0] + dp[1]) % 1000000007;dp[0] = dp[1];dp[1] = dp[2];console.log('i', i, 'dp', dp)}return dp[2];
};

复杂度

• 时间：O(N)
• 空间：O(1)

746. 使用最小花费爬楼梯

解题步骤

• 1 确定dp数组含义：i表示到达第i层，题目求解最小花费，dp[i] 定义为到达第i层最小的花费。并且顶楼是数组长度加一层，dp数组长度为cost数组长度加一。
• 2 递推公式：因为每次可以跳1或者2步，到达第i层方法可以通过i-1(跳1)或i-2(跳2)的方法得到（参考爬楼梯），dp[i]是到达i层最小花费，dp[i-1]和dp[i-2]是到达i-1和i-2层的最小花费，综上可以推出 dp[i] = min( (dp[i - 1] + cost[i-1]), (dp[i - 2] + cost[i - 2]) )
• 3 dp数组初始化：从下标为 0 或下标为 1 的台阶开始，在0/1不花费，只有在此基础往上跳才会花费0/1的值，所以直接站在0/1不花费，dp[0] = 0 dp[1] = 0
• 4 遍历顺序：从前面的数得到后面的结果，从前向后遍历
• 5 打印dp数组

题解

var minCostClimbingStairs = function(cost) {const len = cost.length + 1;const dp = new Array(len).fill(0);for (let i = 2; i < dp.length; i++) {dp[i] = Math.min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));}return dp[len - 1];
};

复杂度

• 时间：O(N)
• 空间：O(N)

优化

使用滚动数组的思想，将空间复杂度优化到 O(1)

var minCostClimbingStairs = function(cost) {// 和求解斐波那契数一样最终结果只和前面两个数有关，可以只保存前两个数的值let pre = 0, curr = 0;const len = cost.length + 1;for (let i = 2; i < len; i++) {const next = Math.min((curr + cost[i - 1]), (pre + cost[i - 2]));pre = curr;curr = next;}return curr;
};

62.不同路径

求解步骤

• 1 确定dp数组含义：dp[i] 到达第i层的方法
• 2 递推公式：dp[i] = dp[i - 1] + dp[i - 2]
• 3 dp数组初始化：dp[1] = 1 dp[2] = 2
• 4 遍历顺序：从前面的数得到后面的结果，从前向后遍历
• 5 打印dp数组

题解

复杂度

• 时间：O(N)
• 空间：O(1)

63.不同路径 II

求解步骤

• 1 确定dp数组含义：dp[i] 到达第i层的方法
• 2 递推公式：dp[i] = dp[i - 1] + dp[i - 2]
• 3 dp数组初始化：dp[1] = 1 dp[2] = 2
• 4 遍历顺序：从前面的数得到后面的结果，从前向后遍历
• 5 打印dp数组

题解

var uniquePaths = function(m, n) {const dp = new Array(m).fill(new Array(n));for (let i = 0; i < m; i++) {dp[i][0] = 1;}for (let i = 0; i < n; i++) {dp[0][n] = 1;}console.log(dp)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];
};uniquePaths(3, 7) // 28

复杂度

• 时间：O(N)
• 空间：O(1)

3、题目汇总

1、线性 DP

198 213 91 1646 1043 139 1869 724

最经典单串：

• 300.最长上升子序列 中等

其他单串

• 32.最长有效括号 困难
• 376.摆动序列
• 368.最大整除子集
• 410.分割数组的最大值

最经典双串：

• 1143.最长公共子序列 中等

其他双串

• 97.交错字符串 中等
• 115.不同的子序列 困难
• 583.两个字符串的删除操作

经典问题：

• 53.最大子序和 简单
• 120.三角形最小路径和 中等
• 152.乘积最大子数组 中等
• 354.俄罗斯套娃信封问题
• 887.鸡蛋掉落（DP+二分） 困难

打家劫舍系列: (打家劫舍3 是树形DP)

• 198.打家劫舍 中等
• 213.打家劫舍 II 中等

股票系列:

• 121.买卖股票的最佳时机
• 122.买卖股票的最佳时机 II
• 123.买卖股票的最佳时机 III
• 188.买卖股票的最佳时机 IV
• 309.最佳买卖股票时机含冷冻期
• 714.买卖股票的最佳时机含手续费

字符串匹配系列

• 72.编辑距离 困难
• 44.通配符匹配 困难
• 10.正则表达式匹配 困难

其他

• 375.猜数字大小 II

2、区间 DP

• 5.最长回文子串 中等
• 516.最长回文子序列
• 87.扰乱字符串 困难
• 312.戳气球 困难
• 730.统计不同回文子字符串
• 1039.多边形三角剖分的最低得分
• 664.奇怪的打印机
• 1246.删除回文子数组

3、背包 DP

• 377.组合总和 Ⅳ
• 416.分割等和子集 (01背包-要求恰好取到背包容量)
• 494.目标和 (01背包-求方案数)
• 322.零钱兑换 (完全背包)
• 518.零钱兑换 II (完全背包-求方案数)
• 474.一和零 (二维费用背包)

4、树形 DP

• 124.二叉树中的最大路径和 困难
• 1245.树的直径 (邻接表上的树形DP)
• 543.二叉树的直径 简单
• 333.最大 BST 子树
• 337.打家劫舍 III 中等

5、状态压缩 DP

• 464.我能赢吗

• 526.优美的排列

• 935.骑士拨号器

• 1349.参加考试的最大学生数

6、数位 DP

• 233.数字 1 的个数 困难
• 902.最大为 N 的数字组合
• 1015.可被 K 整除的最小整数

7、计数型 DP

计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数

• 62.不同路径
• 63.不同路径 II
• 96.不同的二叉搜索树
• 1259.不相交的握手 (卢卡斯定理求大组合数模质数)

8、递推型 DP

• 70.爬楼梯
• 509.斐波那契数
• 576.出界的路径数
• 688.“马”在棋盘上的概率
• 935.骑士拨号器
• 957.N 天后的牢房
• 1137.第 N 个泰波那契数

9、概率型 DP

求概率，求数学期望

• 808.分汤
• 837.新21点

10、博弈型 DP

策梅洛定理，SG 定理，minimax

翻转游戏

• 293.翻转游戏
• 294.翻转游戏 II

Nim游戏

• 292.Nim 游戏

石子游戏

• 877.石子游戏
• 1140.石子游戏 II

井字游戏

• 348.判定井字棋胜负
• 794.有效的井字游戏
• 1275.找出井字棋的获胜者

11、记忆化搜索

本质是 dfs + 记忆化，用在状态的转移方向不确定的情况

• 329.矩阵中的最长递增路径
• 576.出界的路径数