动态规划算法

动态规划解法：

1.确定dp数组以及下标含义

2.确定递推公式

3.dp数组如何初始化

4.如何遍历数组

5.举例推导

例如下面一到简单题

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。 

递归解法 

int fib(int N) {
    if(N<=1)return N;
       return fib(N-1)+fib(N-2);
}

这道斐波那契数列，很多同学直接一手递归就解决，但是递归的时间复杂度O(2^n）明显要高，但是我们今天重点是动态规划 

int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }

可以看到动态规划的时间复杂度是O(N),比递归好了不少，虽然空间复杂度是O(N),但是实际只需要两个变量存放前面的两个值，所以空间复杂度还可以优化到O(1)

int fib(int N) {
        if (N <= 1) return N;
        int dp[2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];