一、动态规划特点
1、求解类型
求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ;
-
求最值 : 最大值 , 最小值 等 ;
- 大规模问题的结果 由 小规模问题 的计算结果 取最大值
- 大规模问题的结果 由 小规模问题 的计算结果 取最小值
-
可行性 : 是否可行 , 只要有一种方案可行即可 ;
- 大规模问题的结果 由 小规模问题 的计算结果 必须全部可行
- 大规模问题的结果 由 小规模问题 的计算结果 只要有一个可行即可
- 大规模问题的结果 由 小规模问题 的计算结果 没有可行结果
-
方案数 : 求一个总数 , 不求具体的方案 ;
- 大规模问题的结果 由 小规模问题 的计算结果 可行方案总数
2、方向性
方向性 : 动态规划 必须有 方向性 , 不能有反复 , 循环依赖 ;
如 : 骑士最短路径问题 , 骑士走 " 日 " 字形 , 可以走 8 个方向 , 在该问题中 , 我们将其行走方向 固定在了右侧的四个方向 , 这样就不会出现循环依赖 ;
如 : 数字三角形 , 在三角形中 , 只能 从上向下走 , 不能向上走 , 这样避免循环依赖 ;
3、动态规划状态选择
动态规划状态选择 : 在 坐标型 动态规划中 , 直接使用 坐标的下标 来标记 相同位置的 状态 ;
状态数组中存储的元素是 :
- 最大值 | 最小值
- 方案数
- 可行性
4、动态规划方程设计
动态规划方程设计 : 动态规划方程 , 最主要的作用是 体现出 下一步坐标状态 与 上一步坐标状态 之间的联系 ;文章来源：https://www.toymoban.com/news/detail-403409.html
也就是 大规模问题解决方案 ( 下一步坐标状态 ) 与 小规模问题解决方案 ( 上一步坐标状态 ) 之间的联系 ;文章来源地址https://www.toymoban.com/news/detail-403409.html
到了这里，关于【算法】动态规划 ⑧ ( 动态规划特点 )的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![6-1 求解资源分配问题（动态规划法）[PTA]](https://imgs.yssmx.com/Uploads/2024/02/523702-1.png)
