DP动态规划问题
2025-07-06 本文已影响0人
voidFan
一、一维DP
1.1 爬楼梯
-
爬楼梯(斐波那契数列)
image.png
-
-
使用最小花费爬楼梯
image.png
-
- 组合总和 Ⅳ 本质是爬楼梯
image.png
- 组合总和 Ⅳ 本质是爬楼梯
1.2 打家劫舍
-
打家劫舍
image.png
-
-
统计放置房子的方式数
image.png
-
-
删除并获得点数
image.png
-
1.3 最值问题
-
最大子数组和
image.png
image.png
-
-
乘积最大子数组
image.png
-
二、二维DP
2.1 基础
- 最小路径和
# 描述：给定一个包含非负整数的 m×n 网格，从左上角到右下角，每次只能向右或向下移动，找出一条路径使得路径上的数字总和最小。
# DP定义：dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。
# 子问题：从上方或左方移动到当前格子的最小和。
# 状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
# 边界条件：dp[0][0] = grid[0][0]
# 第一行和第一列只能从单一方向移动（左或上）。
- 不同路径 dp[i][j] = dp[i-1][j] + dp[i][j-1]
- 不同路径 II dp[i][j] = 0 if grid[i][j] == 1 else dp[i-1][j] + dp[i][j-1]
- 三角形最小路径和 dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
- 下降路径最小和 1573 dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
- 矩阵中移动的最大次数 1626 dp[i][j] = max(dp[k][j-1] + 1) 其中 grid[k][j-1] < grid[i][j]
- 网格中的最小路径代价 1658 dp[i][j] = grid[i][j] + min(dp[i-1][k] + move_cost[grid[i-1][k]][j])
- 下降路径最小和 II 1697 dp[i][j] = matrix[i][j] + min(dp[i-1][k] for k != j)
- 机器人可以获得的最大金币数 1798 dp[i][j] = gold[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])
2.2 进阶
- 矩阵的最大非负积 1807
- 最大得分的路径数目 1853
- 矩阵中和能被 K 整除的路径 1952
- 地下城游戏
- 矩阵中的最长递增路径
- 网格图中递增路径的数目 2001
- 检查是否有合法括号字符串路径 2085
- 扣分后的最大得分 2106
- 最多可收集的水果数目 实际难度 2200
- 摘樱桃 II
- 摘樱桃
- 最长 V 形对角线段的长度 2337 状态设计
- 检查是否有路径经过相同数量的 0 和 1（会员题）
三、背包
0-1 背包 ,每个物品只能选一次。
- 分割等和子集
# 描述：给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
# 将问题转化为0-1背包问题：
# 寻找一个子集，使其和等于总和的一半（即背包容量为sum/2）
# dp[i][j]表示前i个元素能否装满j
# dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j
# 我们的目标就是求出dp[n][target]
- 目标和
- 和为目标值的最长子序列的长度 1659
- 将一个数字表示成幂的和的方案数 1818
- 执行操作可获得的最大总奖励 I 1849
- 一和零 二维背包
- 零数组变换 IV 2068
进阶：
- 零数组变换 IV 2068
- 最后一块石头的重量 II 2092
- 最接近目标价格的甜点成本
- 盈利计划 2204
- 求出所有子序列的能量和 2242
- 最高的广告牌 2381
- 好分区的数目 2415
- 给墙壁刷油漆 2425
- 求出数组中最大序列值 2545
完全背包: 物品可以重复选，无个数限制。
问：关于完全背包，有两种写法.
- 一种是外层循环枚举物品，内层循环枚举体积；
- 另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？
答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。 - 零钱兑换
- 零钱兑换 II
- 完全平方数
- 数位成本和为目标值的最大数字 1927
- 达到总和的方法数量（会员题）混合背包
多重背包（选做）: 物品可以重复选，有个数限制。求方案数
- 获得分数的方法数 1910
- 找到初始输入字符串 II 2629
- 和带限制的子多重集合的数目 2759
分组背包:同一组内的物品至多/恰好选一个。
- 掷骰子等于目标和的方法数 1654
- 最小化目标值与所选元素的差 2010
- 从栈中取出 K 个硬币的最大面值和 2158
四、经典线性 DP
4.1 最长公共子序列（LCS）
讲解：最长公共子序列 编辑距离 一般定义 f[i][j] 表示对 (s[:i],t[:j]) 的求解结果。
- 最长公共子序列
- 两个字符串的删除操作
- 两个字符串的最小 ASCII 删除和
- 编辑距离
- 不相交的线 1806
- 两个子序列的最大点积 1824
- 最高乘法得分 1692
- 不同的子序列
- 从原字符串里进行删除操作的最多次数 2062
- 通过给定词典构造目标字符串的方案数 2082
- 交错字符串
- 最短公共超序列
- 通配符匹配
- 正则表达式匹配
最长递增子序列（LIS）
- 最长递增子序列
- 将三个组排序 1721
- 得到山形数组的最少删除次数 1913
- 找出到每个位置为止最长的有效障碍赛跑路线 1933
- 使数组 K 递增的最少操作次数 1941
