前言

今天我来学一学动态规划，大二的时候学算法分析与设计，觉得算法是真难，有些高不可攀。现在大四了，其实今天稍微学了一下，简单的动态规划问题就和递归差不多，没啥好怕的。加油！
题目链接：小浩算法-动态规划-爬楼梯

我的思路

思路一

这个问题，我觉得可以用递归来做，简直就和斐波拉契数列一模一样，问题在于，当我把n调大一点的时候（比如调成100），程序就跑不出结果了，有点好笑哈哈哈。感觉是内存溢出了，重复的调用太多了，这也是递归的致命缺陷。

根据上面的问题，我们其实可以总结出其实动态规划就是在递归的基础上做出的改进，递归是自顶向下的，而且会有很多重复的调用。但是动态规划一般来说是自底向上的，先求出f(1)，f(2)，f(3）… f(n)，通过一些策略减少了重复子问题的计算，加快了运行效率。

#include<iostream>
using namespace std;class solution {
public:int getMethodNumber(int n) {if (n == 1) {return 1;}else if (n == 2) {return 2;}else {return getMethodNumber(n - 1) + getMethodNumber(n - 2);}}
};
int main() {solution s;cout << s.getMethodNumber(6) << endl;
}

思路二

思路2就是最简单的动态规划了，①从最小的问题开始自底向上（从1开始遍历数组），②把data 存储在数组里面也避免了重复计算的问题。
值得注意的时候，最开始我把函数的返回类型设置为int，把n设置为100时，得到的是负数，哈哈哈哈想到了计组学的东西，马上就把返回类型改成long long了，408学了还是蛮有用的嘛。

实际值：

long long  getMethodNumber_dp(int n) {vector<long long> Arr(n+1);Arr[1] = 1;Arr[2] = 2;for (int i = 3; i <=n; i++) {Arr[i] = Arr[i - 1] + Arr[i - 2];}return Arr[n];
}

我的代码

#include<iostream>
#include<vector>
using namespace std;class solution {
public:int getMethodNumber(int n) {if (n == 1) {return 1;}else if (n == 2) {return 2;}else {return getMethodNumber(n - 1) + getMethodNumber(n - 2);}}long long  getMethodNumber_dp(int n) {vector<long long> Arr(n+1);Arr[1] = 1;Arr[2] = 2;for (int i = 3; i <=n; i++) {Arr[i] = Arr[i - 1] + Arr[i - 2];}return Arr[n];}
};int main() {solution s;cout << s.getMethodNumber(6) << endl;cout << s.getMethodNumber_dp(100) << endl;
}