【SCU-1114】解题报告（DP，路径，DFS）

原始题目

下图是个数字三角，请编写一个程序计算从顶部至底部某处一条路径，使得该路径所经过的数字总和最大。

7

3 8

8 1 0

2 7 4 4

  1. 每一步可沿左斜线向下或右斜线向下走；

  2. 1≤三角形行数≤100

  3. 三角形中的数字为整数 0，1，……，99。

  4. 如果有多种情况结果都最大，任意输出一种即可。

输入：

第一行一个整数N，代表三角形的行数。

接下来N行，描述了一个数字三角。

输出：

第一行一个整数，代表路径所经过底数字总和。

第二行N个数，代表所经过的数字。

样例：

输入：

4 
7
3 8
8 1 0
2 7 4 4

输出：

25 
7 3 8 7

解题思路

入门dp，状态转移方程为dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j]; dp[i][j]表示i行j列（即第i行j个数字到底部的最大和）。根据该状态转移方程递归实现即可。

本题不仅需要记录最终的和，还需要记录路径，这时候就需要根据dp的表再用dfs走一遍。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;
const int maxn=1e2+10; 
int n,m;//n行，m列 
int a[maxn][maxn];
int f[maxn][maxn];
int ans[maxn];
int flag;
//f[i,j]=max(f[i+1,j],f[i+1,j+1])+a[i,j]
int max(int a,int b)
{
	return a>b?a:b;
}
int dp(int i,int j)//递归实现 
{
	int t;
	if(i==n)//到底部
	{
		t=a[i][j];
		return f[i][j]=t;
	}
	else
	{
		t=max(dp(i+1,j),dp(i+1,j+1))+a[i][j];
		return f[i][j]=t;
	} 
}

void dfs(int i,int j,int tot,int n)  
{  
    //cout<<i<<" "<<j<<endl;  
    if(flag)  
        return;  
    if(i==n)  
    {  
        for(int i=1;i<n;i++)  
            printf("%d ",ans[i]);  
        printf("%d\n",ans[n]);  
        flag=1;  
    }  
    int tmp=tot-a[i][j];  
    if(tmp==f[i+1][j])  
    {  
        ans[i+1]=a[i+1][j];  
        dfs(i+1,j,tmp,n);  
    }  
    else if(tmp==f[i+1][j+1])  
    {  
        ans[i+1]=a[i+1][j+1];  
        dfs(i+1,j+1,tmp,n);  
    }  
}  
int main()
{
	while(~scanf("%d",&n))
	{
		

	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dp(1,1);
	printf("%d\n",f[1][1]);
	flag=0;
	dfs(0,0,f[1][1],n);
	}
	return 0;
}

收获与反思

开始在怎么寻找路径这里卡住了，学到的东西得反复看啊。。不然真的不会用。