众所周知，斐波那契数是很多动态规划的教程里面的第一个案例，既简单，简单到即使在不会动态规划的情况下，也可以用动态规划的方法把他做了出来，又经典，小小一个题目包含了动态规划的思想，确实不错。因此，尽管斐波那契数比较简单，我依然选择记录一下，算是作为动态规划的第一个笔记吧。当然，本文仅仅算是我个人的理解，跟大佬们讲的有些许甚至很大的出入，仅供参考。
什么是动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
以上废话摘自维基百科，bb了大半天啥玩意啊，看得一脸懵，我也不会解释。
所以还是以斐波那契数为例吧。
以斐波那契数为例
题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1给你 n ，请计算 F(n) 。题目链接：https://leetcode-cn.com/problems/fibonacci-number
解决问题
首先，题目给了一个公式：F(n) = F(n - 1) + F(n - 2)，这个公式就是递推公式，而所求的 F(n)组成的数组，叫做dp数组，而 F(0) = 0，F(1) = 1，则是dp数组的初始化条件。
那么一切都很明了了，每一项都是前面两项的和，因此我们可以通过这个关系得到dp数组，其中，dp数组的最后一项即为所求 F(n)：
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int[] dp = new int[n];
for (int i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1];
}
}当然，经过观察，可以发现，当前结果仅仅和前面两个结果有关，因此，可以采用滚动数组的思想，把空间复杂度优化成 O(1)，即仅记录dp数组的最后三个数即可：
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int p = 0, q = 0, r = 1;
for (int i = 2; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}题外话——递归法
当然这题也可以使用递归法（貌似也是讲递归的一个经典例子），题外话不多说
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}总结
按照我的理解，动态规划解决的是这么个问题：每一步的结果都与前面的结果相关并且是同一类问题，那么就可以用动态规划解决（我感觉我还是说得很抽象）。
我把动态规划分成了这么几步（自己瞎总结的）：
- 确定dp数组的含义和递推公式
- 搞清楚dp数组的初始化和遍历顺序
- 推导dp数组解决问题
就这么多吧，其实动态规划远远不止斐波那契数这么简单，但是动态规划的思想倒是能通过斐波那契数去理解，说实话这玩意得靠悟，多做几道题就又感觉了。
