动态规划算法

动态规划解法：

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];