动态规划及斐波那契举例

定义：动态规划(Dynamic Programming DP)是一种多阶段决策优化方法，在数学、计算机科学和经济学中使用。
初衷:使用分治法将大问题分解为若干个小问题进行求解。而其中，许多子问题需要重复求解。当 n 很大时效率很低。那么，我们就想到了，能否将已经求解的子问题的解保存下来，再需要使用子问题解的时候，直接给出解，避免进行重复求解，以达到优化算法，降低算法求解时间的目的。

动态规划方法的实质是分治思想和解决冗余：

• 分治思想:将原解问题分解为更小 、 更易求解的子问题，然后对子问题进行求解，并最终产生原问题的解。
• 解决冗余:求解过程中所有子问题只求解一次 并以表的方式保存,对于相同子问题,并不重复求解而通过查表的方式获得。

下面举一个斐波那契数列的例子，分别使用递归非动态规划、递推、递归动态规划三种方式求解。

#include <iostream>using namespace std;// 非动态规划的斐波那契函数
int Fib(int n) {// 第一项和第二项都是1，直接进行返回if (n == 1 || n == 2) {return 1;}// 后一项等于前两项之和return Fib(n - 1) + Fib(n - 2);
}/*** 使用动态规划的斐波那契函数* @param n 数组a中的第几项* @param a 记录数组，将已经求解的记录下来*/
int Fib_DP(int n, int *a) {// a[n]不等于-1时，证明该项已经求解过了，不需要重复进行求解，直接把值返回就行if (a[n] != -1) {return a[n];}else {// a[n]为-1时，证明没有求解过，需要递归进行求解// 求解之后不仅要返回，还要进行记录，避免重复求解a[n] = Fib_DP(n - 1, a) + Fib_DP(n - 2, a);return a[n];}
}int main() {int n = 0;cout << "请输入斐波那契数列的项数 : ";cin >> n;cout << "--------------------------------------------" << endl;cout << "递归非动态规划 : " << Fib(n) << endl;int* a = new int[n];// 前两项的值可以直接得到a[0] = a[1] = 1;// 根据前两项的值，使用关系式，递推的得到结果for (int i = 2; i < n; i++) {a[i] = a[i - 1] + a[i - 2];}cout << "--------------------------------------------" << endl;cout << "使用递推 : " << a[n - 1] << endl;int* dp = new int[n + 1];// 将初始值设置为-1，和赋值过的进行区分for (int i = 0; i < n + 1; i++) {dp[i] = -1;}//前两项设置为1dp[1] = dp[2] = 1;cout << "--------------------------------------------" << endl;cout << "使用递归动态规划 : " << Fib_DP(n,dp) << endl;delete []a;delete []dp;return 0;
}

运行结果: