动态规划详解：从斐波那契数列到数字三角形
动态规划详解：从斐波那契数列到数字三角形
动态规划（Dynamic Programming,DP）是一种用于求解具有最优性质问题的算法。它通过将问题分解为若干子问题，并存储子问题的解来避免重复计算，从而提高算法效率。本文将通过斐波那契数列和数字三角形两个典型例题，详细对比动态规划与贪心算法的差异。
动态规划的基本思想
动态规划（Dynamic Programming,DP）算法通常用于求解某种具有最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原有问题的解。与分治法不同的是，动态规划经分解后得到的子问题往往不是相互独立的。
为什么要使用动态规划算法？
有些问题明明可以用递归实现，为什么还要用动态规划实现呢？下面我们看一个经典的例子：斐波那契数列。
例：斐波那契数列
Fibonacci（斐波那契数列）问题，它是一个简单而典型的分治问题，Fibonacci数列的递归方程表示为：
递归实现代码：
#include<stdio.h>
int main(){
int F(int n);
printf("%d\n",F(5));
return 0;
}
//Fibonacci数列的递归算法
int F(int n){
if(n<=1){
return 1;
}
else{
return F(n-1)+F(n-2);
}
}
该程序实现简单，但是效率非常低。因为在递归调用过程中，有些子问题被反复计算多次，例如：
其中F（3）被计算了两次
F（4）=F（3）+F（2）
F（3）=F（2）+F（1）；
那怎样解决这个问题呢？如果用一个数组保存已解决的子问题的答案，而在需要的时候再从数组中查找出已求得子问题的答案，这样就可以避免大量的重复计算。这种就是动态规划算法：
动态规划算法代码：
#include<stdio.h>
int main(){
int Fibonacci(int n);
printf("%d\n",Fibonacci(5));
return 0;
}
int Fibonacci(int n){
//申请一个数组存放子问题的解
int f[n+1],i;
f[0]=1;
f[1]=1;
for(i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
动态规划算法需要存储各子问题的解，所以它的空间复杂度要大于其他算法，这是一种空间换时间的策略。
怎样使用动态规划算法？
以下是动态规划的求解步骤：
- 分析最优子结构性质（递推关系）
- 递归定义最优值（动态规划核心）
- 自底向上的方式计算出最优值（动态规划的执行过程）
- 根据计算最优值时得到的信息，构造最优解
下面我们将通过一个例子来对比动态规划的应用和贪心算法和动态规划有什么不同。
例：数字三角形
如图所示，有一个群岛，共分为若干层，第1层有一个岛屿,第2层有2个岛屿，……，第n层有n个岛屿。每个岛上都有一块宝，其价值是一个正整数（图中圆圈中的整数)。寻宝者只允许从第一层的岛屿进人，从第n层的岛屿退出，不能后退，他能收集他所经过的所有岛屿上的宝贝。但是，从第i层的岛屿进入第i计1层的岛屿时，有且仅有有2条路径。你的任务是:对于给定的群岛和岛上宝贝的价值，计算一个寻宝者行走一趟所能收集宝贝的最大价值。
这个问题可以抽象为数字三角形问题，要求从顶部出发，在每一个节点可以选择向左走或者向右走，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
我们可以将数字三角形存储在一个二维数组里。
num 0 1 2 3 4
0 9
1 12 15
2 10 6 8
3 2 18 9 5
4 19 7 10 4 16
贪心算法和动态规划的比较：
贪心算法是自顶向下求解，只能选择眼前对自己最有利的一步，其他的路径看不见。
动态规划是自底向上求解，逐层递推。
贪心算法实现：
我们使用贪心算法没法找到真正的最大和（最优解）。是用贪心算法所走的路径为：9+15+8+9+10=51。贪心算法是自顶向下解决问题的，它只能看到眼前的路，并选择对自己最有利的一步，而看不到其他的路径。
对于num[i][j],只需比较num[i+1][j]和num[i+1][j+1]，哪个数字大选择哪条路.
源代码：
//贪心算法实现数字三角形
#include<stdio.h>
int result=0;
int main(){
void tanxin(int a[5][5],int h,int l);//传入数组进行贪心选择 h为行数，l为列数
int i,j;
//数组填入采用初始化的形式(今天不是主角)
int num[5][5]={0};//全部初始化为0
num[0][0]=9;
num[1][0]=12;num[1][1]=15;
num[2][0]=10;num[2][1]=6;num[2][2]=8;
num[3][0]=2;num[3][1]=18;num[3][2]=9;num[3][3]=5;
num[4][0]=19;num[4][1]=7;num[4][2]=10;num[4][3]=4;num[4][4]=16;
//初始化完毕
//输出数组
printf("输出初始化过后的数组\n");
for(i=0;i<5;i++){
for(j=0;j<5;j++){
if(num[i][j]!=0)
printf("%d ",num[i][j]);
}
printf("\n");
}
//贪心选择开始
tanxin(num,5,5);
printf("贪心算法计算的数字和为：%d\n",result);
return 0;
}
void tanxin(int a[5][5],int h,int l){
//拿到数组进行选择
result=a[0][0];
int i,j;
for(i=1;i<h;i++) {
j=i;
if(a[i][j+1]!=0){
if(a[i+1][j]>=a[i+1][j+1]) result=result+a[i+1][j];
else result=result+a[i+1][j+1];
}
}
return result;
}
动态规划实现
我们自底向上，逐层递推，把较大的数字与上一层相加，把得到的数字存到解的数组中（避免重复计算），加到最后就是本题最优解。
例如：
在图中，19+2>7+2,所以把19与上一层相加
自底向上，逐层向上相加，并把计算的结果存储到结果数组中。
对于num[i][j],比较num[i-1][j],num[i-1][j-1]哪个大，num[i][j]与哪个相加
题中我从num[3][0]开始，与下面的num[4][0]与 num[4][1]比较，因为num[4][0]比较大，num[4][0]与num[3][0]相加
源代码：
//动态规划实现数字三角形
#include<stdio.h>
int result=0;
int main(){
//自底向上，眼着全局
int dongtaiguihua(int a[5][5],int h,int l);
//数组填入采用初始化的形式(今天不是主角)
int num[5][5]={0};//全部初始化为0
num[0][0]=9;
num[1][0]=12;num[1][1]=15;
num[2][0]=10;num[2][1]=6;num[2][2]=8;
num[3][0]=2;num[3][1]=18;num[3][2]=9;num[3][3]=5;
num[4][0]=19;num[4][1]=7;num[4][2]=10;num[4][3]=4;num[4][4]=16;
//初始化完毕
result=dongtaiguihua(num,5,5);
printf("动态规划计算的数字和为：%d\n",result);
return 0;
}
int dongtaiguihua(int a[5][5],int h,int l){
int i,j;
for(i=h-2;i>=0;i--){
for(j=0;j<=i;j++){
if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];
else a[i][j]+=a[i+1][j+1];
}
}
return a[0][0];
}
运行结果：