链接

数塔 - http://acm.hdu.edu.cn/showproblem.php?pid=2084

分析

• 自顶而下 —— 总共有 2 n 2^n 2n条路径。因为每一条路径都会一分为二，且初始时刻有1条路径。

• 自底而上 — 路径可逆

• 从哪里来？—— 站在未知的位置上寻求答案
• 到哪里去？—— 站在已知的位置上探索未知领域
• 每一个位置都是一个状态，这些状态反映了之前的情况，且是后续的基础
• 无法用一个有效的贪心策略事先推断出哪一条路径最优
• 求解策略：走一步看一步。在自顶而下的方式下，递推顺序是
  ( 5 , 1 ) 、 ( 5 , 2 ) 、 ( 5 , 3 ) 、 ( 5 , 4 ) 、 ( 5 , 5 ) → {(5,1)、(5,2)、(5,3)、(5,4)、(5,5)}\rightarrow (5,1)、(5,2)、(5,3)、(5,4)、(5,5)→ ( 4 , 1 ) 、 ( 4 , 2 ) 、 ( 4 , 3 ) 、 ( 4 , 4 ) → {(4,1)、(4,2)、(4,3)、(4,4)}\rightarrow (4,1)、(4,2)、(4,3)、(4,4)→ ( 3 , 1 ) 、 ( 3 , 2 ) 、 ( 3 , 3 ) → {(3,1)、(3,2)、(3,3)}\rightarrow (3,1)、(3,2)、(3,3)→ ( 2 , 1 ) 、 ( 2 , 2 ) → {(2,1)、(2,2)}\rightarrow (2,1)、(2,2)→ ( 1 , 1 ) {(1,1)} (1,1)
• 为何高效？

代码

从哪里来？【自顶而下】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MXN 110
int n, dp[MXN][MXN];
int main(){
    int T;
	cin >> T;
    while(T--){		
        scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= i; ++j){
				scanf("%d", dp[i]+j);
			}
		}
		for(int i = n-1; i >= 1; --i) {
			for(int j = 1; j <= i; ++j){
				dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
			}
		}
		printf("%d\n", dp[1][1]);
    }
    return 0;
}

到哪里去？【自顶而下】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MXN 110
int n, d[MXN][MXN], dp[MXN][MXN];
int main(){
    int T;
	cin >> T;
    while(T--){		
        scanf("%d", &n);
		for(int i = 1; i <= n; ++i){
			for(int j = 1; j <= i; ++j){
				scanf("%d", d[i]+j);
			}
		}
		memset(dp, 0, sizeof dp);
		for(int i = 1; i <= n; ++i) dp[n][i] = d[n][i];
		for(int i = n; i > 1; --i) { // 从已知出发
			for(int j = 1; j <= i; ++j){
				dp[i-1][j] = max(dp[i-1][j], dp[i][j]+d[i-1][j]);
				dp[i-1][j-1] = max(dp[i-1][j-1], dp[i][j]+d[i-1][j-1]);
			}
		}
		printf("%d\n", dp[1][1]);
    }
    return 0;
}