关键词：

文章目录

• 一、动态规划场景
• 二、动态规划分类
• • 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 的

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

动态规划三：常见状态与常见递推关系式(代码片段)

动态规划三：常见递推关系式常见状态坐标型前缀划分型前缀匹配型区间型背包型常见递推关系式1D1D\\frac1D1D1D1D​2D0D\\frac2D0D0D2D​2D1D\\frac2D1D1D2D​2D2D\\frac2D2D2D2D​ 常见状态坐标型dp[i]：从起点到坐标i的最值/方案数/可行... 查看详情

动态规划三：常见状态与常见递推关系式(代码片段)

动态规划三：常见递推关系式常见状态坐标型前缀划分型前缀匹配型区间型背包型常见递推关系式1D1D\\frac1D1D1D1D​2D0D\\frac2D0D0D2D​2D1D\\frac2D1D1D2D​2D2D\\frac2D2D2D2D​ 常见状态坐标型dp[i]：从起点到坐标i的最值/方案数/可行... 查看详情

动态规划三：常见状态与常见递推关系式(代码片段)

动态规划三：常见递推关系式常见状态坐标型前缀划分型前缀匹配型区间型背包型常见递推关系式1D1D\\frac1D1D1D1D​2D0D\\frac2D0D0D2D​2D1D\\frac2D1D1D2D​2D2D\\frac2D2D2D2D​ 常见状态坐标型dp[i]：从起点到坐标i的最值/方案数/可行... 查看详情

动态规划(代码片段)

...态规划数字三角形问题尝试使用分治法利用备忘录的递归算法自底向上的动态规划矩阵链乘问题最长公共子序列LCS(LongestCommonSequence)最优二叉搜索树面试中常见的动态规划坐标型动态规划单序列动态规划动态规划数字三角形问题L... 查看详情

动态规划--前缀动态规划问题

【最长公共子序列问题】问题定义：输入：X=(x1,x2,...,xm)，Y=(y1,y2,...yn)输出：公共子序列长度（拓展：如何打印公共子序列）1.如何用子问题表示dp[i][j]表示X的i前缀与Y的j前缀的最长公共子序列长度则总问题==dp[m][n];2.优化子结构... 查看详情

算法动态规划②(动态规划四要素|动态规划状态state|动态规划初始化initialize|动态规划方程function|动态规划答案answer)

...、动态规划答案Answer一、动态规划四要素在上一篇博客【算法】动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)中,不管是自底向上的动态规划还是自顶向下的动态规划,实现动态规划算法时,需要实... 查看详情

算法动态规划②(动态规划四要素|动态规划状态state|动态规划初始化initialize|动态规划方程function|动态规划答案answer)

...、动态规划答案Answer一、动态规划四要素在上一篇博客【算法】动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)中,不管是自底向上的动态规划还是自顶向下的动态规划,实现动态规划算法时,需要实... 查看详情

线性动态规划

注：博客的不少思想是从算法竞赛进阶指南上选取的。线性动态规划是指具有“阶段”划分的动态规划算法。动态规划算法的状态包括多个维度，但在每个维度上都具有“线性”变化的阶段，那么也可以叫作线性动态规划。首先... 查看详情

算法动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)(代码片段)

...态规划简介二、自底向上的动态规划示例1、原理分析2、算法设计3、代码示例三、自顶向下的动态规划示例1、算法设计2、代码示例一、动态规划简介动态规划,英文名称DynamicProgramming,简称DP,不是具体的某种算法,是一种算法思想;... 查看详情

算法动态规划①(动态规划简介|自底向上的动态规划示例|自顶向下的动态规划示例)(代码片段)

...态规划简介二、自底向上的动态规划示例1、原理分析2、算法设计3、代码示例三、自顶向下的动态规划示例1、算法设计2、代码示例一、动态规划简介动态规划,英文名称DynamicProgramming,简称DP,不是具体的某种算法,是一种算法思想;... 查看详情

算法动态规划⑧(动态规划特点)

...,方案数,三者之一,如果求其它内容,则不能使用动态规划算法;求最值:最大值,最小值等;大规模问题的结果由小规模问题的计算结果取最大值大规模问题的结果由小规模问题的计算结果取最小值可行性:是否可行,只要有一种方案可... 查看详情

算法动态规划⑧(动态规划特点)

...,方案数,三者之一,如果求其它内容,则不能使用动态规划算法;求最值:最大值,最小值等;大规模问题的结果由小规模问题的计算结果取最大值大规模问题的结果由小规模问题的计算结果取最小值可行性:是否可行,只要有一种方案可... 查看详情

无人驾驶路径规划局部路径规划-frenet坐标系下的动态轨迹规划(代码片段)

前言：对于无人驾驶路径规划系列的第二篇RRT算法的改进部分，由于有些内容属于个人想到的创新点，有想法投一篇小论文所以暂时没有公开，等后续完成后我会再公开介绍。今天第三篇内容开启一个新的算法介... 查看详情

动态规划算法介绍，以及和贪心算法的比较(代码片段)

##问题描述：1.什么是动态规划算法2.动态规划算法为何能带来效率上的提升3.动态规划算法的特征 ##解决方案：问题1：什么是动态规划算法回答：大约在60多年前，动态规划算法开始出现并大规模使用，动态规划算法的英文... 查看详情

算法动态规划③(leetcode62.不同路径|问题分析|自顶向下的动态规划|自底向上的动态规划)(代码片段)

文章目录一、问题分析二、自顶向下的动态规划1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer5、代码示例三、自底向上的动态规划1、动态规划状态State2、动态规划初始化Initialize3、... 查看详情

算法动态规划③(leetcode62.不同路径|问题分析|自顶向下的动态规划|自底向上的动态规划)(代码片段)

文章目录一、问题分析二、自顶向下的动态规划1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer5、代码示例三、自底向上的动态规划1、动态规划状态State2、动态规划初始化Initialize3、... 查看详情

动态规划2(代码片段)

坐标型115. UniquePathsIIhttps://www.lintcode.com/problem/unique-paths-ii/description?_from=ladder&&fromId=16publicclassSolution/***@paramobstacleGrid:Alistoflistsofintegers*@return:Anintege 查看详情

算法--动态规划

动态规划算法将递归算法写成非递归算法，算法把子问题的答案系统的记录在一个表内。递归算法的三个例子零一背包 完全背包 汽车行驶 查看详情