POJ 1163 The Triangle （DP入门）
今天开始学DP。。这道是基础例题（以下内容参考李文新《程序设计导引及在线实践》）
首先给出这题的递归思路
程序如下：（未用DP，结果是TLE）
#include <stdio.h>
#define MAX_NUM 100
int D[MAX_NUM+10][MAX_NUM+10];
int N;
int MaxSum(int r,int j)
{
if(r==N)
{
return D[r][j];
}
int nSum1=MaxSum(r+1,j);
int nSum2=MaxSum(r+1,j+1);
if(nSum1>nSum2)
return nSum1+D[r][j];
return nSum2+D[r][j];
}
int main(int argc, char *argv[])
{
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
int m;
scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=i;j++)
scanf("%d",&D[i][j]);
printf("%d\n",MaxSum(1,1));
}
这段程序用的是一般递归求解，效率极低，计算次数大约为2^N。
原因在于重复计算。
为了说明重复计算，在程序第9行和第13行加入一句printf("%d,%d\n",r,j);来观察函数调用的过程，改动后的程序如下：
#include <stdio.h>
#define MAX_NUM 20
int D[MAX_NUM+10][MAX_NUM+10];
int N;
int MaxSum(int r,int j)
{
if(r==N)
{
printf("%d,%d\n",r,j);
return D[r][j];
}
int nSum1=MaxSum(r+1,j);
int nSum2=MaxSum(r+1,j+1);
printf("%d,%d\n",r,j);
if(nSum1>nSum2)
return nSum1+D[r][j];
return nSum2+D[r][j];
}
int main(int argc, char *argv[])
{
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
int m;
scanf("%d",&N);
for(int i=1;i<=N;i++)
for(int j=1;j<=i;j++)
scanf("%d",&D[i][j]);
printf("%d\n",MaxSum(1,1));
}
输入题目给的样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
于是输出结果：
5,1 5,2 4,1 5,2 5,3 4,2 3,1 5,2 5,3 4,2 5,3 5,4 4,3 3,2 2,1 5,2 5,3 4,2 5,3 5,4 4,3 3,2 5,3 5,4 4,3 5,4 5,5 4,4 3,3 2,2 1,1 30
这样就很明显了，相同点重复调用的次数很多，若统计成三角形图，则为：
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
因此，重复计算次数极大影响效率。
既然问题出在重复计算，那么解决的办法就是：一个值一旦算出来就要记住，以免重复计算
改良后的程序如下：
#include<stdio.h>
#include<string.h>
#define MAX_NUM 100
int d[MAX_NUM+10][MAX_NUM+10];
int a[MAX_NUM+10][MAX_NUM+10];
int n;
int maxsum(int r,int j)
{
if(r==n)
return d[r][j];
if(a[r+1][j]==-1) a[r+1][j]=maxsum(r+1,j);
if(a[r+1][j+1]==-1) a[r+1][j+1]=maxsum(r+1,j+1);
if(a[r+1][j] > a[r+1][j+1]) return a[r+1][j]+d[r][j];
return a[r+1][j+1]+d[r][j];
}
int main()
{
int i,j;
int max;
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
memset(a,-1,sizeof(a));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
scanf("%d",&d[i][j]);
}
}
printf("%d\n",maxsum(1,1));
}
这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法就叫“动态规划”
实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：
D[r][j] (r=N)
aMaxSum[r][j]=
Max (aMaxSum[r+1][j],aMaxSum[r+1][j+1]) + D[r][j] (r!=N)
因此，仅靠递推也可求得最终aMaxSum[1][1]的值，程序如下：
#include<stdio.h>
#include<string.h>
int main()
{
//freopen("input.txt","rt",stdin);
//freopen("output.txt","wt",stdout);
int d[110][110];
int a[110][110];
int i,j,n;
scanf("%d",&n);
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
scanf("%d", &d[i][j]);
a[i][j]=d[i][j];
}
}
for (i=n;i>1;i-- )
{
for(j=1;j<i;j++)
{
if(a[i][j]<a[i][j+1])
{
a[i-1][j] += a[i][j+1];
}
else
{
a[i-1][j] += a[i][j];
}
}
}
printf("%d\n",a[1][1]);
}
优质内容筛选与推荐>>
1、C#编写COM组件[转]
2、【BZOJ】1685: [Usaco2005 Oct]Allowance 津贴（贪心）
3、webpack2
4、程序阅读理解题目（高中语文版，附答案）
5、13 python --正则