动态规划

前言

动态规划，未刷力扣之前，也弄过几道，当时境界未到，发现特别的难，如今看来，也还是很难，不过，经过小小摸索，
倒是有了一些心得，故此记录一般。

动态规划的问题字眼

一般有如下，求某项的值，求在什么情况下的最优解，多少中情况之类的求接

斐波那契数

https://leetcode-cn.com/problems/fibonacci-number/

斐波那契数，通常用  F(n) 表示，形成的序列称为斐波那契数列。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定  N，计算  F(N)。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

分析

动态规划的常见套路

1. 就是某一项的结果，跟前一项,或者前两项 有某种函数关系
2. 一般前两项的值，没有特定的规律
3. 一般从 dp[i]的第一项，一直求到 dp[n]

针对此题，我们才用我们的套路分析一下，题中给出如下条件都符合我们的套路

1. f(n)=fn(n-1)+fn(n-2)

2. fn(0)=0;fn(1)=1;

实现

   /**
 * @param {number} N
 * @return {number}
 */
var fib = function(N) {
    if(N===0){
        return 0
    }
    if(N===1){
        return 1
    }
    // 一般我们都会把求解第n 项的结果设为dp[i]
    let dp[i]=[]

    // 一般用for 循环 从 第一项 开始
    dp[0]=0;
    dp[1]=1;
    for(let i=2;i<N;i++){
        dp[i]=dp[i-1]+dp[i+2]
    }

    return dp[dp.length-1]

};