关键词：

文章目录

• 一、动态规划四要素
• • 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] 中 ;

• 大规模问题的结果 由 小规模问题 的计算结果 相加
• 大规模问题的结果 由 小规模问题 的计算结果 取最大值
• 大规模问题的结果 由 小规模问题 的计算结果 取最小值
• 大规模问题的结果 由 小规模问题 的计算结果 必须全部可行
• 大规模问题的结果 由 小规模问题 的计算结果 只要有一个可行即可
• 大规模问题的结果 由 小规模问题 的计算结果 没有可行结果
• 大规模问题的结果 由 小规模问题 的计算结果 可行方案总数

动态规划（dynamicprogramming）leetcode经典题目

...的一门重要专业基础课。该学科利用统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。）以局部最优解最终求得全局最优解。在设计动态规划算法时，需要确认原问题与子问题、动态规划状态、边界... 查看详情

核心算法7动态规划算法(代码片段)

动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，最终获得原始问题的解，避免了对交叠子问题的重复求解。在动态规划算法中有三要素：最优子结构... 查看详情

动态规划

...  2.2最优子结构子问题不独立适合，适合动态规划算法设计。 2.3建立递归关系式3.动态规划要素4.备忘录法5.项目实战6.总结 查看详情

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

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

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

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

算法进阶——贪心与动态规划

贪心算法　　贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。　　贪心算法不是对所有问题都能得到整体... 查看详情

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

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

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

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

常见动态规划算法问题策略分析

 本文总结了几种常见动态规划算法的分析策略，但不做案例的具体分析，阅读前最好对这几种算法有一定基础了解。动态规划策略1.动态规划介绍动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转... 查看详情

算法与程序设计：动态规划算法

目录一、概念1.1动态规划算法的基本要素1.2动态规划算法的步骤二、举例2.1矩阵连乘问题2.1.1穷举法2.1.2动态规划法2.1.3例题2.2图像压缩问题2.3最大子段和问题一、概念        动态规划是运筹学的一个分支，是求解多阶段... 查看详情

蓝桥杯——动态规划(代码片段)

动态规划导弹拦截1．动态规划基本概念1.1动态规划三要素阶段﹐状态﹐决策。如果把动态规划的求解过程看成一个工厂的生产线﹐阶段就是生产某个商品的不同的环节，状态就是工件当前的形态﹐决策就是对工件的操作... 查看详情

算法之动态规划（递推求解一）

这篇博客主要讲的是动态规划入门，即动态规划的思想，并且再讲解动态规划的最简单的一个方法。首先，什么是动态规划？　　动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）... 查看详情

c++不知算法系列之初识动态规划算法思想(代码片段)

1.概述动态规划算法应用非常之广泛。对于算法学习者而言，不跨过动态规划这道门，不算真正了解算法。初接触动态规划者，理解其思想精髓会存在一定的难度，本文将通过一个案例，抽丝剥茧般和大家聊聊动态规划。动态规... 查看详情

动态规划

三要素:阶段,状态,决策和转移方程3.边界和答案线性DP背包区间DP树形DP环形DP状态压缩DP倍增优化DP数据结构优化DP单调队列优化DP斜率优化DP四边形不等式优化DP计数类DP数位统计类DP 查看详情

动态规划算法

1、动态规划算法：1）求解过程使用多阶段决策过程，每一步处理一个子问题，可用于求解组合优化问题；2）适用条件：问题需要满足优化原则或最优子结构性质，既：一个最优决策序列的任何子序列本身一定是相对于子序列的... 查看详情

算法动态规划⑤(leetcode63.不同路径ii|问题分析|动态规划算法设计|代码示例)(代码片段)

文章目录一、问题分析二、动态规划算法设计1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer三、代码示例LeetCode63.不同路径II:https://leetcode.cn/problems/unique-paths-ii/一个机器人位于一个mxn... 查看详情

算法动态规划⑤(leetcode63.不同路径ii|问题分析|动态规划算法设计|代码示例)(代码片段)

文章目录一、问题分析二、动态规划算法设计1、动态规划状态State2、动态规划初始化Initialize3、动态规划方程Function4、动态规划答案Answer三、代码示例LeetCode63.不同路径II:https://leetcode.cn/problems/unique-paths-ii/一个机器人位于一个mxn... 查看详情

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

文章目录一、动态规划场景二、动态规划分类1、坐标型动态规划2、前缀划分型动态规划3、前缀匹配型动态规划4、区间型动态规划5、背包型动态规划一、动态规划场景动态规划动态规划使用场景:求最值:最大值,最小值等;大规模... 查看详情