目录
1.动态规划的定义：
动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。
在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果呢。
2.动态规划的特点：
（1）把原来的问题分解成了几个相似的子问题。
（2）所有的子问题都只需要解决一次。
（3）储存子问题的解。
3.动态规划的本质：
是对问题状态的定义和状态转移方程的定义（及状态和状态之间的递归关系）
4.动态规划问题的考虑角度：
（1）状态定义 （要求：定义的状态一定要形成递推关系）
（2）状态间的转移方程定义。
（3）状态的初始化。
（4）返回结果。
5.适用的场景
最值问题，某个东西可不可行，判断是不是的问题，方案的个数。
斐波那契数列
写一个函数，输入 n ，求斐波那（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1
示例 2：
输入：n = 5 输出：5
class Solution {
public int fib(int n) {
final int MOD = 1000000007;
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) % MOD;
}
return r;
}
}版权声明：本文为a1085653724原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。