算法基本思想-动态规划

什么是动态规划（dynamic programming，简称 dp)？

多阶段决策最优解模型，一般使用从下至上的递推方式来获得每个子问题的最优解，从而得到整个问题的最优解

多阶段决策即，一个问题可以分多个子问题。

最优解子结构，即在从下至上的递推过程中每一个子问题一定是全局最优解，因为每个子问题是最优解，那么原问题也就是最优解

根据每个子问题的联系进行求解

这种方式就是迭代递推公式，也称为状态转移方程；定义此方程的核心是定义每个子问题的状态即dp状态

因为从上至下的方式可能存在子问题的重叠，重复的去解相同的子问题，这样复杂度就高了。

动态规划三要素，最优子结构、重叠子问题、状态转移方程。

最重要的步骤为状态转移方程，定义好子问题的状态写出状态转移方程。

1.问题定义为求最值即最大最小问题

2.问题可以采用递归

3.递归过程中存在很多重复子问题

直接看我参考的文章

原问题fibonacci（6）画出的一个自顶向下的的解题方式

是否存在重复子问题这个有眼睛都能看出来

子问题状态即 f(n)

根据子问题状态改用从下至上得到规律

这里这 f(n) = f(n-1) + f(n-2) 即状态转移方程

由于 f(n) 由 f(n-1), f(n-2) 这两个状态转移而来,由于每个子问题只与它前面的两个状态，所以我们只要定义三个变量

所以最终

算法（Algorithm）

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！