动态规划

前言

刷 LeetCode 的时候，发现有种算法：动态规划（Dynamic Programming），查阅了资料，简单梳理一下动态规划是啥？

动态规划（Dynamic Programming）

用途：主要用来解决希望找到问题最优解的优化问题

判断是否能够使用该算法：

1. 答案能不能构成数列
2. 取决于该问题拆解成小问题时，这些“小问题”会不会被重复调用

举例：

1. 契波那契数列 0,1,1,2,3,5,8,13 … ：它的每个数字都与前两个紧邻的数字相关，如果 F(n) 是第 n 个数字，那么会有 F(n) = F(n - 1) + F(n - 2)。这个在数学上称作 递归方程 或者 递推关系。为了计算后面的项，它需要前面项的计算结果作为输入。

2. 小青蛙跳台阶问题：它可以跳 1 阶 或 2 阶，设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

   1. 当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法；

   2. 当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。

   f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2) ，以上递推性质为斐波那契数列。本题可转化为 求斐波那契数列第 n 项的值 ，与 斐波那契数列 等价，唯一的不同在于起始数字不同。

   • 青蛙跳台阶问题： f(0)=1，f(1)=1，f(2)=2；
   • 斐波那契数列问题： f(0)=0，f(1)=1，f(2)= 1

有话要说

目前做的题量不够多，网上的资料有点晦涩，实在比较懵逼，现表达自己现阶段的理解，希望往后做多了题能够对动态规划有更深、更不一样的看法。 2020.8.5