POJ1163 the Triangle

原题链接:POJ1163

题目大意:数字三角形,从上走到下,只能向下走或向右走,找到路径权值之和最小值。

数字三角形$dp$

$f[i][j]$ 表示从最下往上走,走到 $(i,j)$ 位置路径和的最小值,每次只可以由下或右下转移而来,$f[1][1]$ 为答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int f[N][N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
			cin >> f[i][j];
    }
	for (int i = n; i >= 1; i--) {
        for (int j = i; j >= 1; j--)
			f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
    }
	cout << f[1][1] << endl;
	return 0;
}
updatedupdated2020-05-112020-05-11
加载评论
点击刷新