Skip to content

Latest commit

 

History

History
222 lines (213 loc) · 57.1 KB

dynamic-programming.md

File metadata and controls

222 lines (213 loc) · 57.1 KB

动态规划

全部标签

数据结构

数组 矩阵 链表 双向链表 单调栈 队列 单调队列 堆(优先队列) 哈希表 字符串 字符串匹配 二叉树 二叉搜索树 最小生成树 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程


题号 标题 题解 标签 难度 力扣
5 最长回文子串 [✓] 双指针 字符串 动态规划 🟠 🀄️ 🔗
10 正则表达式匹配 [✓] 递归 字符串 动态规划 🔴 🀄️ 🔗
22 括号生成 [✓] 字符串 动态规划 回溯 🟠 🀄️ 🔗
32 最长有效括号 [✓] 字符串 动态规划 🔴 🀄️ 🔗
42 接雨水 [✓] 数组 双指针 2+ 🔴 🀄️ 🔗
44 通配符匹配 [✓] 贪心 递归 字符串 1+ 🔴 🀄️ 🔗
45 跳跃游戏 II [✓] 贪心 数组 动态规划 🟠 🀄️ 🔗
53 最大子数组和 [✓] 数组 分治 动态规划 🟠 🀄️ 🔗
55 跳跃游戏 [✓] 贪心 数组 动态规划 🟠 🀄️ 🔗
62 不同路径 [✓] 数学 动态规划 组合数学 🟠 🀄️ 🔗
63 不同路径 II [✓] 数组 动态规划 矩阵 🟠 🀄️ 🔗
64 最小路径和 [✓] 数组 动态规划 矩阵 🟠 🀄️ 🔗
70 爬楼梯 [✓] 记忆化搜索 数学 动态规划 🟢 🀄️ 🔗
72 编辑距离 [✓] 字符串 动态规划 🟠 🀄️ 🔗
85 最大矩形 [✓] 数组 动态规划 2+ 🔴 🀄️ 🔗
87 扰乱字符串 字符串 动态规划 🔴 🀄️ 🔗
91 解码方法 [✓] 字符串 动态规划 🟠 🀄️ 🔗
95 不同的二叉搜索树 II [✓] 二叉搜索树 动态规划 2+ 🟠 🀄️ 🔗
96 不同的二叉搜索树 [✓] 二叉搜索树 数学 2+ 🟠 🀄️ 🔗
97 交错字符串 [✓] 字符串 动态规划 🟠 🀄️ 🔗
115 不同的子序列 [✓] 字符串 动态规划 🔴 🀄️ 🔗
118 杨辉三角 [✓] 数组 动态规划 🟢 🀄️ 🔗
119 杨辉三角 II [✓] 数组 动态规划 🟢 🀄️ 🔗
120 三角形最小路径和 [✓] 数组 动态规划 🟠 🀄️ 🔗
121 买卖股票的最佳时机 [✓] 数组 动态规划 🟢 🀄️ 🔗
122 买卖股票的最佳时机 II [✓] 贪心 数组 动态规划 🟠 🀄️ 🔗
123 买卖股票的最佳时机 III [✓] 数组 动态规划 🔴 🀄️ 🔗
124 二叉树中的最大路径和 [✓] 深度优先搜索 动态规划 1+ 🔴 🀄️ 🔗
131 分割回文串 [✓] 字符串 动态规划 回溯 🟠 🀄️ 🔗
132 分割回文串 II [✓] 字符串 动态规划 🔴 🀄️ 🔗
139 单词拆分 [✓] 字典树 记忆化搜索 数组 3+ 🟠 🀄️ 🔗
140 单词拆分 II [✓] 字典树 记忆化搜索 数组 4+ 🔴 🀄️ 🔗
152 乘积最大子数组 [✓] 数组 动态规划 🟠 🀄️ 🔗
174 地下城游戏 [✓] 数组 动态规划 矩阵 🔴 🀄️ 🔗
188 买卖股票的最佳时机 IV [✓] 数组 动态规划 🔴 🀄️ 🔗
198 打家劫舍 [✓] 数组 动态规划 🟠 🀄️ 🔗
213 打家劫舍 II [✓] 数组 动态规划 🟠 🀄️ 🔗
221 最大正方形 [✓] 数组 动态规划 矩阵 🟠 🀄️ 🔗
233 数字 1 的个数 [✓] 递归 数学 动态规划 🔴 🀄️ 🔗
241 为运算表达式设计优先级 [✓] 递归 记忆化搜索 数学 2+ 🟠 🀄️ 🔗
256 粉刷房子 🔒 数组 动态规划 🟠 🀄️ 🔗
264 丑数 II [✓] 哈希表 数学 动态规划 1+ 🟠 🀄️ 🔗
265 粉刷房子 II 🔒 数组 动态规划 🔴 🀄️ 🔗
276 栅栏涂色 🔒 动态规划 🟠 🀄️ 🔗
279 完全平方数 [✓] 广度优先搜索 数学 动态规划 🟠 🀄️ 🔗
294 翻转游戏 II 🔒 记忆化搜索 数学 动态规划 2+ 🟠 🀄️ 🔗
300 最长递增子序列 [✓] 数组 二分查找 动态规划 🟠 🀄️ 🔗
309 买卖股票的最佳时机含冷冻期 [✓] 数组 动态规划 🟠 🀄️ 🔗
312 戳气球 数组 动态规划 🔴 🀄️ 🔗
313 超级丑数 [✓] 数组 数学 动态规划 🟠 🀄️ 🔗
322 零钱兑换 [✓] 广度优先搜索 数组 动态规划 🟠 🀄️ 🔗
329 矩阵中的最长递增路径 [✓] 深度优先搜索 广度优先搜索 5+ 🔴 🀄️ 🔗
333 最大二叉搜索子树 🔒 深度优先搜索 二叉搜索树 2+ 🟠 🀄️ 🔗
337 打家劫舍 III [✓] 深度优先搜索 动态规划 1+ 🟠 🀄️ 🔗
338 比特位计数 [✓] 位运算 动态规划 🟢 🀄️ 🔗
343 整数拆分 [✓] 数学 动态规划 🟠 🀄️ 🔗
351 安卓系统手势解锁 🔒 位运算 动态规划 回溯 1+ 🟠 🀄️ 🔗
354 俄罗斯套娃信封问题 [✓] 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
357 统计各位数字都不同的数字个数 [✓] 数学 动态规划 回溯 🟠 🀄️ 🔗
361 轰炸敌人 🔒 数组 动态规划 矩阵 🟠 🀄️ 🔗
368 最大整除子集 [✓] 数组 数学 动态规划 1+ 🟠 🀄️ 🔗
375 猜数字大小 II [✓] 数学 动态规划 博弈 🟠 🀄️ 🔗
376 摆动序列 [✓] 贪心 数组 动态规划 🟠 🀄️ 🔗
377 组合总和 Ⅳ [✓] 数组 动态规划 🟠 🀄️ 🔗
392 判断子序列 [✓] 双指针 字符串 动态规划 🟢 🀄️ 🔗
396 旋转函数 [✓] 数组 数学 动态规划 🟠 🀄️ 🔗
397 整数替换 [✓] 贪心 位运算 记忆化搜索 1+ 🟠 🀄️ 🔗
403 青蛙过河 数组 动态规划 🔴 🀄️ 🔗
410 分割数组的最大值 贪心 数组 二分查找 2+ 🔴 🀄️ 🔗
413 等差数列划分 [✓] 数组 动态规划 滑动窗口 🟠 🀄️ 🔗
416 分割等和子集 [✓] 数组 动态规划 🟠 🀄️ 🔗
418 屏幕可显示句子的数量 🔒 数组 字符串 动态规划 🟠 🀄️ 🔗
435 无重叠区间 [✓] 贪心 数组 动态规划 1+ 🟠 🀄️ 🔗
446 等差数列划分 II - 子序列 数组 动态规划 🔴 🀄️ 🔗
458 可怜的小猪 [✓] 数学 动态规划 组合数学 🔴 🀄️ 🔗
464 我能赢吗 [✓] 位运算 记忆化搜索 数学 3+ 🟠 🀄️ 🔗
465 最优账单平衡 🔒 位运算 数组 动态规划 2+ 🔴 🀄️ 🔗
466 统计重复个数 字符串 动态规划 🔴 🀄️ 🔗
467 环绕字符串中唯一的子字符串 [✓] 字符串 动态规划 🟠 🀄️ 🔗
471 编码最短长度的字符串 🔒 字符串 动态规划 🔴 🀄️ 🔗
472 连接词 深度优先搜索 字典树 数组 2+ 🔴 🀄️ 🔗
473 火柴拼正方形 [✓] 位运算 数组 动态规划 2+ 🟠 🀄️ 🔗
474 一和零 [✓] 数组 字符串 动态规划 🟠 🀄️ 🔗
486 预测赢家 [✓] 递归 数组 数学 2+ 🟠 🀄️ 🔗
487 最大连续1的个数 II 🔒 数组 动态规划 滑动窗口 🟠 🀄️ 🔗
488 祖玛游戏 广度优先搜索 记忆化搜索 2+ 🔴 🀄️ 🔗
494 目标和 [✓] 数组 动态规划 回溯 🟠 🀄️ 🔗
509 斐波那契数 [✓] 递归 记忆化搜索 数学 1+ 🟢 🀄️ 🔗
514 自由之路 [✓] 深度优先搜索 广度优先搜索 字符串 1+ 🔴 🀄️ 🔗
516 最长回文子序列 [✓] 字符串 动态规划 🟠 🀄️ 🔗
518 零钱兑换 II [✓] 数组 动态规划 🟠 🀄️ 🔗
526 优美的排列 [✓] 位运算 数组 动态规划 2+ 🟠 🀄️ 🔗
542 01 矩阵 [✓] 广度优先搜索 数组 动态规划 1+ 🟠 🀄️ 🔗
546 移除盒子 记忆化搜索 数组 动态规划 🔴 🀄️ 🔗
552 学生出勤记录 II 动态规划 🔴 🀄️ 🔗
553 最优除法 数组 数学 动态规划 🟠 🀄️ 🔗
562 矩阵中最长的连续1线段 🔒 数组 动态规划 矩阵 🟠 🀄️ 🔗
568 最大休假天数 🔒 数组 动态规划 矩阵 🔴 🀄️ 🔗
576 出界的路径数 动态规划 🟠 🀄️ 🔗
583 两个字符串的删除操作 [✓] 字符串 动态规划 🟠 🀄️ 🔗
600 不含连续1的非负整数 动态规划 🔴 🀄️ 🔗
629 K 个逆序对数组 动态规划 🔴 🀄️ 🔗
634 寻找数组的错位排列 🔒 数学 动态规划 🟠 🀄️ 🔗
638 大礼包 [✓] 位运算 记忆化搜索 数组 3+ 🟠 🀄️ 🔗
639 解码方法 II 字符串 动态规划 🔴 🀄️ 🔗
646 最长数对链 [✓] 贪心 数组 动态规划 1+ 🟠 🀄️ 🔗
647 回文子串 双指针 字符串 动态规划 🟠 🀄️ 🔗
650 两个键的键盘 数学 动态规划 🟠 🀄️ 🔗
651 四个键的键盘 🔒 数学 动态规划 🟠 🀄️ 🔗
656 成本最小路径 🔒 数组 动态规划 🔴 🀄️ 🔗
664 奇怪的打印机 字符串 动态规划 🔴 🀄️ 🔗
673 最长递增子序列的个数 [✓] 树状数组 线段树 数组 1+ 🟠 🀄️ 🔗
678 有效的括号字符串 [✓] 贪心 字符串 1+ 🟠 🀄️ 🔗
688 骑士在棋盘上的概率 动态规划 🟠 🀄️ 🔗
689 三个无重叠子数组的最大和 [✓] 数组 动态规划 🔴 🀄️ 🔗
691 贴纸拼词 位运算 数组 字符串 3+ 🔴 🀄️ 🔗
698 划分为k个相等的子集 位运算 记忆化搜索 数组 3+ 🟠 🀄️ 🔗
712 两个字符串的最小ASCII删除和 [✓] 字符串 动态规划 🟠 🀄️ 🔗
714 买卖股票的最佳时机含手续费 [✓] 贪心 数组 动态规划 🟠 🀄️ 🔗
718 最长重复子数组 数组 二分查找 动态规划 3+ 🟠 🀄️ 🔗
727 最小窗口子序列 🔒 字符串 动态规划 滑动窗口 🔴 🀄️ 🔗
730 统计不同回文子序列 字符串 动态规划 🔴 🀄️ 🔗
740 删除并获得点数 [✓] 数组 哈希表 动态规划 🟠 🀄️ 🔗
741 摘樱桃 数组 动态规划 矩阵 🔴 🀄️ 🔗
746 使用最小花费爬楼梯 [✓] 数组 动态规划 🟢 🀄️ 🔗
750 角矩形的数量 🔒 数组 数学 动态规划 1+ 🟠 🀄️ 🔗
764 最大加号标志 数组 动态规划 🟠 🀄️ 🔗
787 K 站中转内最便宜的航班 深度优先搜索 广度优先搜索 3+ 🟠 🀄️ 🔗
788 旋转数字 数学 动态规划 🟠 🀄️ 🔗
790 多米诺和托米诺平铺 [✓] 动态规划 🟠 🀄️ 🔗
792 匹配子序列的单词数 字典树 数组 哈希表 4+ 🟠 🀄️ 🔗
799 香槟塔 动态规划 🟠 🀄️ 🔗
801 使序列递增的最小交换次数 数组 动态规划 🔴 🀄️ 🔗
805 数组的均值分割 位运算 数组 数学 2+ 🔴 🀄️ 🔗
808 分汤 数学 动态规划 概率与统计 🟠 🀄️ 🔗
813 最大平均值和的分组 数组 动态规划 前缀和 🟠 🀄️ 🔗
818 赛车 动态规划 🔴 🀄️ 🔗
823 带因子的二叉树 数组 哈希表 动态规划 1+ 🟠 🀄️ 🔗
828 统计子串中的唯一字符 哈希表 字符串 动态规划 🔴 🀄️ 🔗
834 树中距离之和 深度优先搜索 1+ 🔴 🀄️ 🔗
837 新 21 点 数学 动态规划 滑动窗口 1+ 🟠 🀄️ 🔗
838 推多米诺 双指针 字符串 动态规划 🟠 🀄️ 🔗
845 数组中的最长山脉 [✓] 数组 双指针 动态规划 1+ 🟠 🀄️ 🔗
847 访问所有节点的最短路径 位运算 广度优先搜索 2+ 🔴 🀄️ 🔗
871 最低加油次数 贪心 数组 动态规划 1+ 🔴 🀄️ 🔗
873 最长的斐波那契子序列的长度 [✓] 数组 哈希表 动态规划 🟠 🀄️ 🔗
877 石子游戏 数组 数学 动态规划 1+ 🟠 🀄️ 🔗
879 盈利计划 数组 动态规划 🔴 🀄️ 🔗
887 鸡蛋掉落 数学 二分查找 动态规划 🔴 🀄️ 🔗
894 所有可能的真二叉树 递归 记忆化搜索 2+ 🟠 🀄️ 🔗
898 子数组按位或操作 位运算 数组 动态规划 🟠 🀄️ 🔗
902 最大为 N 的数字组合 数组 数学 字符串 2+ 🔴 🀄️ 🔗
903 DI 序列的有效排列 字符串 动态规划 前缀和 🔴 🀄️ 🔗
907 子数组的最小值之和 数组 动态规划 1+ 🟠 🀄️ 🔗
913 猫和老鼠 拓扑排序 记忆化搜索 3+ 🔴 🀄️ 🔗
918 环形子数组的最大和 [✓] 队列 数组 分治 2+ 🟠 🀄️ 🔗
920 播放列表的数量 数学 动态规划 组合数学 🔴 🀄️ 🔗
926 将字符串翻转到单调递增 字符串 动态规划 🟠 🀄️ 🔗
931 下降路径最小和 [✓] 数组 动态规划 矩阵 🟠 🀄️ 🔗
935 骑士拨号器 动态规划 🟠 🀄️ 🔗
940 不同的子序列 II 字符串 动态规划 🔴 🀄️ 🔗
943 最短超级串 位运算 数组 字符串 2+ 🔴 🀄️ 🔗
956 最高的广告牌 数组 动态规划 🔴 🀄️ 🔗
960 删列造序 III 数组 字符串 动态规划 🔴 🀄️ 🔗
964 表示数字的最少运算符 记忆化搜索 数学 动态规划 🔴 🀄️ 🔗
968 监控二叉树 深度优先搜索 动态规划 1+ 🔴 🀄️ 🔗
975 奇偶跳 数组 动态规划 2+ 🔴 🀄️ 🔗
978 最长湍流子数组 数组 动态规划 滑动窗口 🟠 🀄️ 🔗
983 最低票价 [✓] 数组 动态规划 🟠 🀄️ 🔗
996 平方数组的数目 位运算 数组 哈希表 4+ 🔴 🀄️ 🔗
1000 合并石头的最低成本 数组 动态规划 前缀和 🔴 🀄️ 🔗
1012 至少有 1 位重复的数字 数学 动态规划 🔴 🀄️ 🔗
1014 最佳观光组合 [✓] 数组 动态规划 🟠 🀄️ 🔗
1024 视频拼接 贪心 数组 动态规划 🟠 🀄️ 🔗
1025 除数博弈 [✓] 脑筋急转弯 数学 动态规划 1+ 🟢 🀄️ 🔗
1027 最长等差数列 [✓] 数组 哈希表 二分查找 1+ 🟠 🀄️ 🔗
1031 两个非重叠子数组的最大和 数组 动态规划 滑动窗口 🟠 🀄️ 🔗
1035 不相交的线 [✓] 数组 动态规划 🟠 🀄️ 🔗
1039 多边形三角剖分的最低得分 数组 动态规划 🟠 🀄️ 🔗
1043 分隔数组以得到最大和 数组 动态规划 🟠 🀄️ 🔗
1048 最长字符串链 数组 哈希表 双指针 3+ 🟠 🀄️ 🔗
1049 最后一块石头的重量 II [✓] 数组 动态规划 🟠 🀄️ 🔗
1062 最长重复子串 🔒 字符串 二分查找 动态规划 3+ 🟠 🀄️ 🔗
1066 校园自行车分配 II 🔒 位运算 数组 动态规划 2+ 🟠 🀄️ 🔗
1067 范围内的数字计数 🔒 数学 动态规划 🔴 🀄️ 🔗
1092 最短公共超序列 [✓] 字符串 动态规划 🔴 🀄️ 🔗
1105 填充书架 数组 动态规划 🟠 🀄️ 🔗
1125 最小的必要团队 位运算 数组 动态规划 1+ 🔴 🀄️ 🔗
1130 叶值的最小代价生成树 贪心 数组 2+ 🟠 🀄️ 🔗
1137 第 N 个泰波那契数 [✓] 记忆化搜索 数学 动态规划 🟢 🀄️ 🔗
1139 最大的以 1 为边界的正方形 数组 动态规划 矩阵 🟠 🀄️ 🔗
1140 石子游戏 II 数组 数学 动态规划 2+ 🟠 🀄️ 🔗
1143 最长公共子序列 [✓] 字符串 动态规划 🟠 🀄️ 🔗
1147 段式回文 贪心 双指针 字符串 3+ 🔴 🀄️ 🔗
1155 掷骰子等于目标和的方法数 动态规划 🟠 🀄️ 🔗
1162 地图分析 广度优先搜索 数组 动态规划 1+ 🟠 🀄️ 🔗
1182 与目标颜色间的最短距离 🔒 数组 二分查找 动态规划 🟠 🀄️ 🔗
1186 删除一次得到子数组最大和 数组 动态规划 🟠 🀄️ 🔗
1187 使数组严格递增 数组 二分查找 动态规划 1+ 🔴 🀄️ 🔗
1191 K 次串联后最大子数组之和 数组 动态规划 🟠 🀄️ 🔗