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;
}

POJ1163 the Triangle

相关文章：