添柴12146数字金字塔

lyt0707

标题:	1.5-1数字金字塔
详情:	观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。         7       3   8     8   1   0   2   7   4   4 4   5   2   6   5

http://bbs.codeaha.com/problem-12146.html

这题我一样用三种方式：普通dfs,记忆化dfs,和动态规划

1.普通dfs:

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. int a[1001][1001]={0},n,cnt;
   
5. int dfs(int x,int y)
   
6. {
   
7.         if (x==n)//边界值
   
8.         {
   
9.                 return a[x][y];返回
   
10.         }
    
11.         return max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];//上面+右上角
    
12. }
    
13. int main()
    
14. {
    
15.         int i,j;
    
16.         scanf("%d",&n);
    
17.         for(i=1;i<=n;i++)
    
18.         {
    
19.                 for(j=1;j<=i;j++)
    
20.                 {
    
21.                         scanf("%d",&a[i][j]);
    
22.                 }
    
23.         }
    
24.         printf("%d",dfs(1,1));
    
25.         return 0;
    
26. }

复制代码

2.记忆化dfs

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. int a[1001][1001]={0},n,cnt,f[1001][1001]={0};
   
5. int dfs(int x,int y)
   
6. {
   
7.         if(f[x][y]==-1)
   
8.         {
   
9.                 f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];//记忆化
   
10.         }
    
11.         return f[x][y];返回值
    
12. }
    
13. 
    
14. int main()
    
15. {
    
16.        
    
17.         int i,j;
    
18.        
    
19.         scanf("%d",&n);
    
20.         for(i=1;i<=n;i++)
    
21.         {
    
22.                 for(j=1;j<=i;j++)
    
23.                 {
    
24.                         scanf("%d",&a[i][j]);//读入
    
25.                         f[i][j]=-1;
    
26.                 }
    
27.         }
    
28.        
    
29.         for(i=1;i<=n;i++)
    
30.                 f[n][i]=a[n][i];
    
31.                
    
32.         printf("%d",dfs(1,1));
    
33.         return 0;
    
34. }

复制代码

3.动态规划：

1. #include <cstdio>
   
2. int main()
   
3. {
   
4.     int n,a[1001][1001],d[1001][1001],i,j,k;
   
5.     scanf("%d",&n);
   
6.     for(i=1;i<=n;i++)
   
7.     {
   
8.         for(j=1;j<=i;j++)
   
9.         {
   
10.             scanf("%d",&d[i][j]);
    
11.         }
    
12.     }
    
13.     for(j=1;j<=n;j++)
    
14.     {
    
15.         a[n][j]=d[n][j];
    
16.     }
    
17.     for(i=n-1;i>=1;i--)
    
18.     {
    
19.         for(j=1;j<=i;j++)
    
20.         {
    
21.             if(a[i+1][j+1]>a[i+1][j]) //分类
    
22.             {
    
23.                 a[i][j]=d[i][j]+a[i+1][j+1];选择右上角
    
24.             }
    
25.             else
    
26.             {
    
27.                 a[i][j]=d[i][j]+a[i+1][j];选择上面
    
28.             }
    
29.         }
    
30.     }
    
31.     printf("%d",a[1][1]);
    
32.     return 0;
    
33. }

复制代码

创世菌

动规大法好！

Forinser

都很好啊！！！长知识的！！！！！