【算法】动态规划 ④ ( 动态规划分类 | 坐标型动态规划 | 前缀划分型动态规划 | 前缀匹配型动态规划 | 区间型动态规划 | 背包型动态规划 )

文章目录

• 一、动态规划场景
• 二、动态规划分类
• • 1、坐标型动态规划
  • 2、前缀划分型动态规划
  • 3、前缀匹配型动态规划
  • 4、区间型动态规划
  • 5、背包型动态规划

一、动态规划场景

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

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

二、动态规划分类

动态规划分类 :

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

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

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 的

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