文章目录
- 一、动态规划四要素
- 1、动态规划状态 State
- 2、动态规划初始化 Initialize
- 3、动态规划方程 Function
- 4、动态规划答案 Answer
一、动态规划四要素
在上一篇博客 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 ) 中 , 不管是 自底向上的动态规划 还是 自顶向下的动态规划 , 实现 动态规划 算法时 , 需要实现 4 个步骤 , 分别是
- 状态 State
- 初始化 Initialize
- 方程 Function
- 答案 Answer
1、动态规划状态 State
动态规划 的 状态 State , 与 递归的定义 对应 ;
使用 一维数组 f[i] 或者 二维数组 f[i][j] 表示 特定条件下 规模更小 的问题的答案 ;
使用 i 或 i , j 参数 将 大规模的问题 划分成 小规模问题 ;
一维数组 f[i] 或者 二维数组 f[i][j] 中的元素值 可能是 :
- 某个小规模问题的 最大值 结果
- 某个小规模问题的 最小值 结果
- 方案可行性 , 如 : 是 True 或 否 False 的 布尔值
上一篇博客 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 ) 中 , 动态规划 状态 State 就是 二维数组 dp , dp[i][j] 表示从 第 i 行 第 j 列的元素出发 , 数组的元素值就是走到最底层的最短路径 ; 是 小规模问题的 最小值结果 ;
2、动态规划初始化 Initialize
动态规划 的 初始化 Initialize , 与 递归的出口 对应 ;
当 大规模问题 无法 拆解成 小规模问题 时的 最小状态 , 就是 动态规划初始化 Initialize ;
在 自底向上 的 动态规划 中 , 初始化 就是 最底层 的数据 ;
在 自顶向下 的 动态规划 中 , 初始化 就是 最顶层 的数据 ;
另外 无法代入 到 动态规划方程 Function 中的数据 , 也要并入到 动态规划初始化 Initialize 范畴中 , 对这部分数据也要进行初始化操作 ; 如 : 上一篇博客 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 ) 中 自顶向下的动态规划示例 中 , 对 数字三角形 左右两边 的 两列 数据进行初始化 操作 ;
3、动态规划方程 Function
动态规划 的 方程 Function , 与 递归的拆解 对应 ;
动规方程 主要用于 描述 大规模问题 如何 拆解成 小规模问题 , 即 大规模问题 是 如何 依赖于 小规模问题的 , 如 :
- 大规模问题的结果 由 小规模问题 的计算结果 相加
- 大规模问题的结果 由 小规模问题 的计算结果 取最大值
- 大规模问题的结果 由 小规模问题 的计算结果 取最小值
- 大规模问题的结果 由 小规模问题 的计算结果 必须全部可行
- 大规模问题的结果 由 小规模问题 的计算结果 只要有一个可行即可
- 大规模问题的结果 由 小规模问题 的计算结果 没有可行结果
- 大规模问题的结果 由 小规模问题 的计算结果 可行方案总数
小规模问题的 结果 存放在 一维数组 f[i] 或者 二维数组 f[i][j] 中 ;
4、动态规划答案 Answer
动态规划 的 答案 Answer , 与 递归的调用 对应 ;
动态规划 方程 执行后 , 得到 一堆 小规模问题的计算结果 , 小规模问题的 结果 存放在 一维数组 f[i] 或者 二维数组 f[i][j] 中 ;
- 大规模问题的结果 由 小规模问题 的计算结果 相加
- 大规模问题的结果 由 小规模问题 的计算结果 取最大值
- 大规模问题的结果 由 小规模问题 的计算结果 取最小值
- 大规模问题的结果 由 小规模问题 的计算结果 必须全部可行
- 大规模问题的结果 由 小规模问题 的计算结果 只要有一个可行即可
- 大规模问题的结果 由 小规模问题 的计算结果 没有可行结果
- 大规模问题的结果 由 小规模问题 的计算结果 可行方案总数
