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

文章目录

• 一、动态规划特点
• • 1、求解类型
  • 2、方向性
  • 3、动态规划状态选择
  • 4、动态规划方程设计

一、动态规划特点

1、求解类型

求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ;

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

2、方向性

方向性 : 动态规划 必须有 方向性 , 不能有反复 , 循环依赖 ;

如 : 骑士最短路径问题 , 骑士走 " 日 " 字形 , 可以走 8 个方向 , 在该问题中 , 我们将其行走方向 固定在了右侧的四个方向 , 这样就不会出现循环依赖 ;

在这里插入图片描述

如 : 数字三角形 , 在三角形中 , 只能 从上向下走 , 不能向上走 , 这样避免循环依赖 ;

在这里插入图片描述

3、动态规划状态选择

动态规划状态选择 : 在 坐标型 动态规划中 , 直接使用 坐标的下标 来标记 相同位置的 状态 ;

状态数组中存储的元素是 :

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

4、动态规划方程设计

动态规划方程设计 : 动态规划方程 , 最主要的作用是 体现出 下一步坐标状态 与 上一步坐标状态 之间的联系 ;

也就是 大规模问题解决方案 ( 下一步坐标状态 ) 与 小规模问题解决方案 ( 上一步坐标状态 ) 之间的联系 ;