“动态规划算法求解步骤 动态规划算法要不要排序”

本篇文章775字，读完约2分钟

一个，

想法:

在空之间变更时间。

首先，不看动态规划法，了解递归法。 递归方法的逻辑很简单。 “处理父母的问题，必须先处理孩子的问题，再处理孩子的问题”，但是如果有两个以上的子问题，调用同一个孙子问题，或者无故浪费时间，或者多次调用，都有可能造成浪费。 因此，动态规划方法应运而生。 处理这种浪费时间的方法如下。

留下处理的问题，每次直接打电话，都可以省去很多重复。

接下来，

三个主要步骤

为了确立状态排列dp，动态计划的通常的思想是状态。 任何一种情况下，该状态都会存储在相应的数组f[i][j]中。 而且这一步也很重要。 只有理解“状态”的概念时，才能采用状态转移方程式。

2状态迁移方程的通常形式为数组形式。 以“数字三角形”( digitaltriangle ) [2]为例，此问题的状态转变方程式为dp[i][j]=(dp[i，j]、dp[i 1，j] a[i] )

上一个问题dp[i][j]会对下一个问题产生什么影响？ 各状态的数学表示可以用三个参数z，I和j表示为z=dp[i][j] .这三个参数z表示这一状态的大小. 通常，I表示该状态的编号，j通常表示该状态的条件。

有两个因素影响“状态”数组。 一个是之前的状态，没什么可说的。 递归总是这样。 二是状态转换的“价格”，价格通常是我们最先投入的，比如爬楼梯所需的高度，摘苹果需要体力等。

三个循环。 因为整个状态数组构建过程需要经过扫描过程(扫描I变量)。 在这个过程中，各状态有很多可能性( j变量的扫描)，所以明确的扫描是第三个关键。 通过明确这三个关键点，可以明确整个核心算法。

三大要素

/把所有的价格都储蓄起来

状态阵列dp[n][m]//收纳各状态

状态转换方程式f(dp )//的公式是该状态=f (该状态或之前的状态成本) f最小或最大等状态的选择方法