DP动态规划问题

一、一维DP

1.1 爬楼梯

    1. 爬楼梯(斐波那契数列)


      image.png

    1. 使用最小花费爬楼梯


      image.png
    1. 组合总和 Ⅳ 本质是爬楼梯
      image.png

1.2 打家劫舍

    1. 打家劫舍


      image.png

    1. 统计放置房子的方式数


      image.png

    1. 删除并获得点数


      image.png

1.3 最值问题

    1. 最大子数组和


      image.png

      image.png

    1. 乘积最大子数组


      image.png

二、二维DP

2.1 基础

    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]
#           第一行和第一列只能从单一方向移动（左或上）。
    1. 不同路径 dp[i][j] = dp[i-1][j] + dp[i][j-1]
    1. 不同路径 II dp[i][j] = 0 if grid[i][j] == 1 else dp[i-1][j] + dp[i][j-1]
    1. 三角形最小路径和 dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
    1. 下降路径最小和 1573 dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
    1. 矩阵中移动的最大次数 1626 dp[i][j] = max(dp[k][j-1] + 1) 其中 grid[k][j-1] < grid[i][j]
    1. 网格中的最小路径代价 1658 dp[i][j] = grid[i][j] + min(dp[i-1][k] + move_cost[grid[i-1][k]][j])
    1. 下降路径最小和 II 1697 dp[i][j] = matrix[i][j] + min(dp[i-1][k] for k != j)
    1. 机器人可以获得的最大金币数 1798 dp[i][j] = gold[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1])

2.2 进阶

  1. 矩阵的最大非负积 1807
  2. 最大得分的路径数目 1853
  3. 矩阵中和能被 K 整除的路径 1952
  4. 地下城游戏
  5. 矩阵中的最长递增路径
  6. 网格图中递增路径的数目 2001
  7. 检查是否有合法括号字符串路径 2085
  8. 扣分后的最大得分 2106
  9. 最多可收集的水果数目 实际难度 2200
  10. 摘樱桃 II
  11. 摘樱桃
  12. 最长 V 形对角线段的长度 2337 状态设计
  13. 检查是否有路径经过相同数量的 0 和 1（会员题）

三、背包

0-1 背包 ,每个物品只能选一次。

    1. 分割等和子集
# 描述：给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
# 将问题转化为0-1背包问题：
# 寻找一个子集，使其和等于总和的一半（即背包容量为sum/2）
# dp[i][j]表示前i个元素能否装满j
# dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j
# 我们的目标就是求出dp[n][target]
    1. 目标和
    1. 和为目标值的最长子序列的长度 1659
    1. 将一个数字表示成幂的和的方案数 1818
    1. 执行操作可获得的最大总奖励 I 1849
    1. 一和零 二维背包
    1. 零数组变换 IV 2068
      进阶：
    1. 最后一块石头的重量 II 2092
    1. 最接近目标价格的甜点成本
    1. 盈利计划 2204
    1. 求出所有子序列的能量和 2242
    1. 最高的广告牌 2381
    1. 好分区的数目 2415
    1. 给墙壁刷油漆 2425
    1. 求出数组中最大序列值 2545

完全背包: 物品可以重复选，无个数限制。

问：关于完全背包，有两种写法.

  • 一种是外层循环枚举物品，内层循环枚举体积；
  • 另一种是外层循环枚举体积，内层循环枚举物品。如何评价这两种写法的优劣？
    答：两种写法都可以，但更推荐前者。外层循环枚举物品的写法，只会遍历物品数组一次；而内层循环枚举物品的写法，会遍历物品数组多次。从 cache 的角度分析，多次遍历数组会导致额外的 cache miss，带来额外的开销。所以虽然这两种写法的时间空间复杂度是一样的，但外层循环枚举物品的写法常数更小。
    1. 零钱兑换
    1. 零钱兑换 II
    1. 完全平方数
    1. 数位成本和为目标值的最大数字 1927
    1. 达到总和的方法数量（会员题）混合背包

多重背包（选做）: 物品可以重复选，有个数限制。求方案数

    1. 获得分数的方法数 1910
    1. 找到初始输入字符串 II 2629
    1. 和带限制的子多重集合的数目 2759

分组背包:同一组内的物品至多/恰好选一个。

    1. 掷骰子等于目标和的方法数 1654
    1. 最小化目标值与所选元素的差 2010
    1. 从栈中取出 K 个硬币的最大面值和 2158

四、经典线性 DP

4.1 最长公共子序列（LCS）

讲解：最长公共子序列 编辑距离 一般定义 f[i][j] 表示对 (s[:i],t[:j]) 的求解结果。

    1. 最长公共子序列
    1. 两个字符串的删除操作
    1. 两个字符串的最小 ASCII 删除和
    1. 编辑距离
    1. 不相交的线 1806
    1. 两个子序列的最大点积 1824
    1. 最高乘法得分 1692
    1. 不同的子序列
    1. 从原字符串里进行删除操作的最多次数 2062
    1. 通过给定词典构造目标字符串的方案数 2082
    1. 交错字符串
    1. 最短公共超序列
    1. 通配符匹配
    1. 正则表达式匹配

最长递增子序列（LIS）

    1. 最长递增子序列
    1. 将三个组排序 1721
    1. 得到山形数组的最少删除次数 1913
    1. 找出到每个位置为止最长的有效障碍赛跑路线 1933
    1. 使数组 K 递增的最少操作次数 1941
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容