DP算法清单

DP算法清单

---

一、入门 DP

1.1. 爬楼梯

题号	题目	是否完成	国内公司	备注
70	爬楼梯	✅		⭐
509	斐波那契数	✅
746	使用最小花费爬楼梯	✅	字节
1137	第 N 个泰波那契数	✅	字节、腾讯
377	组合总和 Ⅳ	✅	字节、华为、京东
2466	统计构造好字符串的方案数	✅	字节
2266	统计打字方案数	✅	字节
2533	好二进制字符串的数量	✅

1.2. 打家劫舍

题号	题目	是否完成	国内公司	备注
198	打家劫舍	✅	字节、腾讯、华为 百度、同花顺、网易 京东、高德	⭐
213	打家劫舍 II	✅	字节、B站、腾讯 华为、微信
2320	统计放置房子的方式数	✅	字节
3186	施咒的最大总伤害	❌
2140	解决智力问题	❌

1.3. 最大子数组和（最大子段和）

题号	题目	是否完成	国内公司	备注
53	最大子数组和	❌
2606	找到最大开销的子字符串	❌
1749	任意子数组和的绝对值的最大值	❌
1191	K 次串联后最大子数组之和	❌
918	环形子数组的最大和	❌
2321	拼接数组的最大分数	❌
152	乘积最大子数组	❌
1186	删除一次得到子数组最大和	❌
3381	长度可被 K 整除的子数组的最大元素和	❌

网格图 DP

题号	题目	是否完成	备注
62	不同路径	❌	⭐
63	不同路径 II	❌
64	最小路径和	❌	⭐
120	三角形最小路径和	❌
931	下降路径最小和	❌
1289	下降路径最小和 II	❌
1594	矩阵的最大非负积	❌
1301	最大得分的路径数目	❌
174	地下城游戏	❌	⭐
329	矩阵中的最长递增路径	❌	⭐
2328	网格图中递增路径的数目	❌
2267	检查是否有合法括号字符串路径	❌
1937	扣分后的最大得分	❌
1463	摘樱桃 II	❌
741	摘樱桃	❌

---

背包 DP

0-1 背包

题号	题目	是否完成	备注
416	分割等和子集	❌	⭐
494	目标和	❌	⭐
474	一和零	❌
1049	最后一块石头的重量 II	❌
879	盈利计划	❌
956	最高的广告牌	❌

完全背包

题号	题目	是否完成	备注
322	零钱兑换	❌	⭐
518	零钱兑换 II	❌
279	完全平方数	❌

分组背包

题号	题目	是否完成	备注
1155	掷骰子的 N 种方法	❌
2218	从栈中取出 K 个硬币的最大面值和	❌

---

区间 DP

题号	题目	是否完成	备注
516	最长回文子序列	❌	⭐
1312	让字符串成为回文串的最少插入次数	❌
1547	切棍子的最小成本	❌
1039	多边形三角剖分的最低得分	❌
312	戳气球	❌	⭐
1000	合并石头的最低成本	❌

---

状态机 DP

股票问题

题号	题目	是否完成	备注
121	买卖股票最佳时机	❌	⭐
122	买卖股票 II	❌
123	买卖股票 III	❌
188	买卖股票 IV	❌
309	含冷冻期股票	❌
714	含手续费股票	❌

---

状压 DP

题号	题目	是否完成	备注
526	优美的排列	❌
698	划分为 k 个相等子集	❌
1125	最小的必要团队	❌
1349	参加考试的最大学生数	❌
1434	每个人戴不同帽子的方案数	❌

---

数位 DP

题号	题目	是否完成	备注
233	数字 1 的个数	❌
600	不含连续1的非负整数	❌
902	最大为 N 的数字组合	❌
1012	至少有 1 位重复的数字	❌

---

树形 DP

题号	题目	是否完成	备注
337	打家劫舍 III	❌	⭐
124	二叉树中的最大路径和	❌	⭐
543	二叉树的直径	❌
2246	相邻字符不同的最长路径	❌

---

数据结构优化 DP

题号	题目	是否完成	备注
1425	带限制的子序列和	❌
1696	跳跃游戏 VI	❌
239	滑动窗口最大值	❌
2944	购买水果需要的最少金币数	❌