本篇其实是去年的时候在部门内部做的一次简单的分享的内容，也是对自己坚持学习了一个多月的动态规划内容的一些简单的总结和整理
从斐波那契数列到01背包问题
起始
在正式介绍动态规划之前，我们先从一个简单且不陌生的题目开始
斐波那契数列
首先我们来看下这个题目
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1这里我们题面已经明确的给出了实现的逻辑了，是的，就是一眼就能看出来的递归。
最基本的实现代码如下，非常的简单，也很好理解
class Solution {
public int fib(int n) {
if (n<2){
return n;
}
return fib(n-1) + fib(n-2);
}
}但是，真的就这样结束了么？显然不是，首先我们能直观的看到这个是一个递归的过程，如果输入的n不是很大尚且还好，但是当你的n足够大的时候，比如20000?虽然这也不是非常大，那么会发生什么呢？
此时也许你会说，那我可以改jvm参数，增大可用栈深度，那你的栈深度又能增加到多少呢？200万？还是2000万？ 我们不妨仔细分析一下这个过程
F( n ) = F(n - 1) + F(n - 2)
F( n - 1 ) = F(n - 2) + F(n - 3)
F( n - 2 ) = F(n - 5) + F(n - 4)
F( n - 3 ) = F(n - 4) + F(n - 5)可以很容易的看出来，中间经历的大量的重复运算，思考一下，我们是不是有什么办法能把这个中间的大量的重复运算的过程省略过去呢？
这个时候你也许会想到哈希表，是的，这个方向是对的，不过在面对这种int的key的时候，我们一般有一种更加简单更加轻便的作法来实现哈希表的功能，那就是数组。我们可以声明一个int[]的数组来实现我们需要的功能，且其本身比Map型数据结构更加的轻便简单，相对的速度也更快
而且，这个过程中，我们不再是从F(N)向F(0)求解，而是正向的从0向N求解，那么代码如下
class Solution {
public int fib(int n) {
if (n<2){
return n;
}
int[] dp = new int[n+1];
dp[1] = 1;
int idx = 1;
while (++idx <=n){
dp[idx] = dp[idx-1] + dp[idx-2];
}
return dp[n];
}
}我们在算法中，给这样这种的数组一个独特的名字叫滚动数组，这样是不是就规避了最大栈深度的限制了呢？那我们入参给个Integer.MAX_VALUE看看会发生什么？内部的值相加是否会超出int型上限我们姑且先不论，直接入参给入跑一下看看
那么接下来我们要对这份代码再做一点优化，而数组长度上限的问题，你可以自己再思考下看看这个问题"java中数组的长度上限是多少"而又为什么会有这个上限。
拓展小知识：循环遍历和递归是可以相互转化的，最经典的例子莫过于二叉树的深度优先搜索(DFS)和广度优先搜索(BFS)，一个是递归遍历，一个是循环遍历，这是另外一个不小的话题，这里不做展开讨论了现在我们再次观察下这份代码，n位置的值，只和n-1和n-2位置的值有关，那么我们就确实没有必要声明一个长度为n+1的数组，对此我们做一点点修改
