POJ 3716 Cow Bowling 数字三角形简单DP

照抄刘汝佳的《算法竞赛入门经典》（较薄的那本）P159 数字三角形

两种写法，一个是记忆化搜索，一个是DP，其实之所以要用DP是因为解这个题时出现了大量重叠的子问题

用d(i,j)记录从第i 行，第j列出发（从上往下）能得到的最大和（包括自己）

转移方程为d(i,j) = a(i,j) + max(d(i+1,j) , d(i+1,j+1));

还有一个问题就是关于#define max(a,b) a<b?a:b的用法

如果写这样的式子 t = a + max(c,d),怀疑会出错，因为下面的递推式我本来没有写max()函数而是用的这个宏定义，但是就错了，一直出不来正确的结果，还不符合"交换律"

就是写成形如t = max(c,d)+a;结果还会不一样，很是纳闷，求解释。。。。一定要用这个宏定义写的话，据实践得，可以这样写上面的式子，t = max(c,d);t+=a;这样是一定不会错的了

贴代码：

记忆化搜索：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 355
 4 int a[N][N],d[N][N];
 5 int n;
 6 int max(int x,int y)
 7 {
 8     return x>y?x:y;
 9 }
10 int dfs(int x,int y)
11 {
12     if(d[x][y] != -1) return d[x][y];//如果d[x][y]已经算过，不再重复计算，直接返回结果即可
13     if(x == n-1) return d[x][y]=a[x][y];//最底层，答案就是本身，边界条件
14     return d[x][y] = a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));//递归求解
15 }
16 int main()
17 {
18     freopen("in.cpp","r",stdin);
19     scanf("%d",&n);
20     for(int i=0; i<n; ++i)
21         for(int j=0; j<=i; ++j)
22             scanf("%d",&a[i][j]);
23     memset(d,-1,sizeof(d));//记住赋初始值，表明所有的值还未被计算过
24     printf("%d\n",dfs(0,0));
25     return 0;
26 }

DP：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 355
 4 int a[N][N],d[N];
 5 int n;
 6 int max(int x,int y)
 7 {
 8     return x>y?x:y;
 9 }
10 int main()
11 {
12 //    freopen("in.cpp","r",stdin);
13     scanf("%d",&n);
14     for(int i=0; i<n-1; ++i)
15         for(int j=0; j<=i; ++j)
16             scanf("%d",&a[i][j]);
17     for(int j=0; j<n; ++j)
18         scanf("%d",&d[j]);
19     for(int i=n-2; i>=0; --i)//逆推
20         for(int j=0; j<=i; ++j)
21             d[j] = a[i][j] + max(d[j],d[j+1]);//为节省点空间，因为逆推的时候下一行不会再用了，所以直接用一行存d
22     printf("%d\n",d[0]);
23     return 0;
24 }

POJ 3716 Cow Bowling 数字三角形 简单DP

POJ 3716 Cow Bowling 数字三角形简单DP