一、动态规划场景

动态规划 动态规划使用场景 :

• 求最值 : 最大值 , 最小值 等 ;
  • 大规模问题的结果 由 小规模问题 的计算结果相加
  • 大规模问题的结果 由 小规模问题 的计算结果取最大值
  • 大规模问题的结果 由 小规模问题 的计算结果取最小值
• 可行性 : 是否可行 , 只要有一种方案可行即可 ;
  • 大规模问题的结果 由 小规模问题 的计算结果必须全部可行
  • 大规模问题的结果 由 小规模问题 的计算结果只要有一个可行即可
  • 大规模问题的结果 由 小规模问题 的计算结果没有可行结果
• 方案数 : 求一个总数 , 不求具体的方案 ;
  • 大规模问题的结果 由 小规模问题 的计算结果可行方案总数

二、动态规划分类

动态规划分类 :

• 坐标型 动态规划, 又分为 一维坐标 动态规划 , 二维坐标 动态规划 ;
• 前缀型 动态规划该类型动态规划有分为如下两种类型 ;
  • 前缀划分型动态规划
  • 前缀匹配型动态规划
• 背包型 动态规划
• 区间型 动态规划

不同类型的 动态规划 中 ,状态值 的表示形式不同 , 将动态规划 的 状态 表示形式 确定, 该问题基本就可以解决 ;

1、坐标型动态规划

坐标型 动态规划 , 又分为一维坐标 动态规划 ,二维坐标 动态规划 ;

• 一维坐标 动态规划 , 使用一维数组 dp 表示状态,dp[i] 表示 从 起点坐标位置 开始 到坐标 i 位置 的最大值 | 最小值 |方案数 |可行性 ;
• 二维坐标 动态规划 , 使用二维数组 dp 表示状态 ,dp[i][j] 表示 从 起点坐标位置 开始 到坐标 ( i , j ) 位置 的最大值 | 最小值 |方案数 |可行性 ;

其中 方案数 也可以作为 可行性标准 ,方案数 大于 0 就是可行 ,方案数 等于 0 就是不可行 ;

坐标型动态规划 , 典型的题目是 三角形最小路径和 , 不同路径 ;

• LeetCode 120.三角形最小路径和 : https://leetcode.cn/problems/triangle/
• LeetCode 62.不同路径 : https://leetcode.cn/problems/unique-paths/

此类动态规划中 ,坐标信息就是状态信息 的下标,坐标 与 状态 基本是一致的 ;

• 一维坐标 对应 一维数组 状态信息
• 二维坐标 对应 二维数组 状态信息
• 三维坐标 对应 三维数组 状态信息

2、前缀划分型动态规划

前缀划分型 动态规划 , 又分为如下两个类型 :

• 使用一维数组 dp 表示状态,dp[i] 表示 前 i 个字符 构成的 前缀串 的最大值 | 最小值 |方案数 |可行性 ;
• 使用二维数组 dp 表示状态 ,dp[i][j] 表示 前 i 个字符 构成的 前缀串 划分为 j 个部分 的最大值 | 最小值 |方案数 |可行性 ;

前缀划分型动态规划示例 :

• LeetCode 139. 单词拆分 : https://leetcode.cn/problems/word-break/
• LeetCode 140. 单词拆分 II : https://leetcode.cn/problems/word-break-ii/

3、前缀匹配型动态规划

前缀划分型 动态规划 : 使用二维数组 dp 表示状态,dp[i][j]表示第一个字符串 的 前 i 个字符 构成的 前缀串与 第二个字符串 的前 j 个 字符构成的前缀串可以匹配上的

• 最大值 | 最小值
• 方案数
• 可行性 ;

前缀匹配型动态规划示例 :

• LeetCode 1143. 最长公共子序列 : https://leetcode.cn/problems/longest-common-subsequence/
• LeetCode 44. 通配符匹配 : https://leetcode.cn/problems/wildcard-matching/

前缀匹配型动态规划 与 前缀型动态规划 区别是 :

• 坐标型的动态规划 : 走到某个坐标时 , 有某种 最值 , 方案数 , 可行性 结果 ;
• 前缀型的动态规划 : 字符串的前 i 个字符构成的 前缀串 , 有某种 最值 , 方案数 , 可行性 结果 ;

4、区间型动态规划

区间型动态规划 : 使用二维数组 dp 表示状态,dp[i][j]表示区间 i 到 j的

• 最大值 | 最小值
• 方案数
• 可行性 ;

区间型动态规划特点是 , 范围较大的区间的结果 , 依赖于 范围较小的区间的结果 ;

区间型动态规划示例 :

• LeetCode 877. 石子游戏 : https://leetcode.cn/problems/stone-game/
• LeetCode 312. 戳气球 : https://leetcode.cn/problems/burst-balloons/

5、背包型动态规划

背包型动态规划 : 使用二维数组 dp 表示状态,dp[i][j]表示 从前 i 个物品中选出一些物品组合之后 和为 j的

• 最大值 | 最小值
• 方案数
• 可行性 ;