递归时间开销较大 动态规划主要的思想是：在程序运行过程中，将一些数据存放在表中，后面用到此数据时，直接调用，避免了重复计算问题。
相关题目
1. 斐波那契系数
f(1) = f(2) = 1;
f(n) = f(n-1) + f(n-2);
（leetcode中限制了 n<30）
法一： 暴力递归 O(2n)
public: int f1(int n)
{
if(n < 1)
return 0;
if(n==1 || n==2)
return 1;
return f1(n-1) + f1(n-2);
}
leetcode 结果：
法二：动态规划 O(N)
从左到右依次求出每一项的值，通过顺序计算，得到第n项即可。
class Solution {
public:
int fib(int n) {
if(n<0)
return 0;
if(n==1 || n==2)
return 1;
int a1 = 1;
int a2 = 1;
int b = 0;
for(int i=3; i<=n; i++)
{
b = a1 + a2;
a1 = a2;
a2 = b;
}
return b;
}
};
leetcode 结果：
2.爬楼梯问题
问题描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 ：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
思路：在爬第n层台阶时，要么从第（n-1）层台阶迈一个台阶； 要么从第（n-2）层台阶，一次迈2个台阶；
所以，第n阶的方法 = 到第（n-1）阶的方法 + 到第（n-2）阶的方法；
与斐波那契系数问题相同，只是初始值不同。
法一：暴力递归
class Solution {
public:
int climbStairs(int n) {
if(n<0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
return climbStairs(n-1) + climbStairs(n-2);
}
};
leetcode运行结果： 由于对于 n 的大小没有限制，所以运行超出时间限制
法二：动态规划
class Solution {
public:
int climbStairs(int n) {
if(n<0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
int a1 = 1;
int a2 = 2;
int b = 0;
for(int i=3; i<=n; i++)
{
b = a1 + a2;
a1 = a2;
a2 = b;
}
return b;
}
};
leetcode运行结果：
3.矩阵最小路径和
leetcode 第64题，题目描述:
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
方法一：动态规划
思路：定义一个辅助数组dp，数组大小和给定数组相同，dp[i][j]记录从（0,0）点到（i, j）点的最短路径，则最终我们想要的结果就是 dp[m-1][n-1]。对于第一行来说，因为只能往右走，所以，dp[0][j]就是前面的累加 + 此位置的value；对于第一列来说，只能往下走，dp[i][0] 也是前面的累加 + 此位置的value；对于其他的位置，那就等于 【它左边和它上面】这二者的最小值+此位置的value;
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.empty())
return 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int> > dp(n,vector<int>(n));//记录从（0，0）走到（i，j）的最短路径
dp[0][0] = grid[0][0];
for(int j=1; j<n; j++)
dp[0][j] = dp[0][j-1] + grid[0][j];
for(int i=1; i<m; i++)
dp[i][0] += dp[i-1][0] + grid[i][0];
for(int i=1; i<m; i++)
for(int j=1; j<n; j++)
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
return dp[m-1][n-1];
}
};
leetcode 结果： 时间复杂度：O(m x n); 空间复杂度：O(m x n);
