动态规划是一个比较巧妙的算法思想。在进行解释其含义之前，我们先搞几个例子来引出动态规划的思想。

一、斐波那契数列（Fibonacci sequence）

Fibonacci数列问题是一个经典的可以分解为若干个子问题解决的算法问题。

1、简单递归法

#include <ctime>#include <iostream>using namespace std;/** *  0 1 1 2 3 5 8 13 21 *  递归的方式 */int fib1(int n){	if(n == 0){		return 0;	}	if(n == 1){		return 1;	}	return fib1(n -1) + fib1(n-2);}int main() {	int n = 20;	time_t startTime = clock();	int sum = fib1(n);	time_t endTime = clock();	cout << "the sum is:"<< sum << ",take time is:" << double(endTime - startTime) / CLOCKS_PER_SEC  << endl; 	return 0;}

运行结果为：

其方法是非常耗时的，因为有许多计算是重复了的。

2、记忆搜索法

记忆化搜索-自上而下地解决问题。

#include <ctime>#include <iostream>#include <vector>using namespace std;vector<int> memo;/** *  0 1 1 2 3 5 8 13 21 *  记忆化搜索 思考的过程是从顶到下 */int fib(int n){	if(n == 0){		return 0;	}	if(n == 1){		return 1;	}	if(memo[n] == -1){		memo[n] = fib(n -1) + fib(n -2);	}	return memo[n];}int main() {	int n = 40;	memo = vector<int>(n+1, -1);	time_t startTime = clock();	int sum = fib(n);	time_t endTime = clock();	cout << "the sum is:"<< sum << ",take time is:" << double(endTime - startTime) / CLOCKS_PER_SEC  << endl; 	return 0;}

3、动态规划法

动态规划-自下向上的解决问题。

在进行解释前先引用一下维基百科的解释：

动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

#include <ctime>#include <iostream>#include <vector>using namespace std;vector<int> memo;/** *  0 1 1 2 3 5 8 13 21 *  动态规划 思考的过程是从底到上 */int fib(int n){	memo[0] = 0;	memo[1] = 1;	for(int i = 2; i <= n; i++){		memo[i] = memo[i - 1] + memo[i - 2];	}	return memo[n];}int main() {	int n = 40;	memo = vector<int>(n+1, -1);	time_t startTime = clock();	int sum = fib(n);	time_t endTime = clock();	cout << "the sum is:"<< sum << ",take time is:" << double(endTime - startTime) / CLOCKS_PER_SEC  << endl; 	return 0;}

运行的结果和上面记忆搜索的一样。

4、总结一下2种不同方法的思想

二、下面以leetcode 第70题climbing-stairs为例子1、题源爬楼梯

链接如下：

2、问题分析分解

爬上n阶台阶可以拆分为2部分，爬上n-1阶台阶的问题加上爬上n-2阶台阶的问题。

3、记忆搜索法

#include <iostream>#include <vector>using namespace std;/// 70. Climbing Stairs///  记忆搜索法/// 时间复杂度: O(n)/// 空间复杂度: O(n)class Solution{private:	vector<int> memo;	int calaWays(int n){			if(n == 0 || n == 1){				return 1;			}			if(memo[n] == -1){				memo[n] = calaWays(n - 1) + calaWays(n - 2);			}			return memo[n];		}public:	int climbStairs(int n){		memo = vector<int>(n+1, -1);		return calaWays(n);	}};int main() {	int n = 40;	time_t startTime = clock();	int sum = Solution().climbStairs(n);	time_t endTime = clock();	cout << "the sum is:"<< sum << ",take time is:" << double(endTime - startTime) / CLOCKS_PER_SEC  << endl;	return 0;}

运行结果：

4、动态规划法

#include <iostream>#include <vector>using namespace std;/// 70. Climbing Stairs///  动态规划/// 时间复杂度: O(n)/// 空间复杂度: O(n)class Solution{private:	vector<int> memo;	int calaWays(int n){			memo[0] = 1;			memo[1] = 1;			for(int i = 2; i <= n; i++){				memo[i] = memo[i - 1] + memo[i -2];			}			return memo[n];		}public:	int climbStairs(int n){		memo = vector<int>(n+1, -1);		return calaWays(n);	}};int main() {	int n = 40;	time_t startTime = clock();	int sum = Solution().climbStairs(n);	time_t endTime = clock();	cout << "the sum is:"<< sum << ",take time is:" << double(endTime - startTime) / CLOCKS_PER_SEC  << endl;	return 0;}

运行的结果和上面的一样。

5、类似的问题

还有如下2题：

1、

2、

有兴趣的可以搞一下。