『鐘万北』08.ダイナミックプランニング:三角形上の最大パスカウントC++

まず,三角形上の最大経路個数を計算するためには,まず最大経路を解くアルゴリズムを制定しなければならない.
(y,x)の位置では、直接下の数字または右下の数字(y+1,x)と(y+1,x+1)の中に大きな数字を見つけてから下に進むことができます.

演算を実行すると,(b)と同じ結果が得られる.

ここで最大経路の個数は、9−7−3−5、9−7−3−5、9−7−2−6の3つである.
(0,0)からの最大パスは(1,0)と(1,1)どちらを下に行くべきか分かりやすい
path 2(1,1)>path 2(1,0)のため、常に(1,1)まで下がるのが有利である.したがって,(0,0)からの最大パス数は,(1,1)からの最大パス数に常に等しい.
(1,1)では、2つの下降可能なセルで作成できる最大パスの和が同じであるため、どの方向に下降しても最大パスを作成できます.
したがって,2つの位置からの最短経路の個数を合わせると,(1,1)からの最大経路の個数となる.
count(y,x)=(y,x)から最下行までの最大パス数で、このような点火式を作成できます.

#include<iostream>
#include<algorithm>
using namespace std;

int n, triangle[100][100];
int cache[100][100];
int countCache[100][100];

int path2(int y, int x) {
	if (y == n - 1) return triangle[y][x];

	int& ret = cache[y][x];
	if (ret != -1) return ret;

	return ret = max(path2(y + 1, x), path2(y + 1, x + 1)) + triangle[y][x];
}

int count(int y, int x) {
	if (y == n - 1) return 1;

	int& ret = countCache[y][x];
	if (ret != -1) return ret;

	ret = 0;

	if (path2(y + 1, x + 1) >= path2(y + 1, x)) ret += count(y + 1, x + 1);
	if (path2(y + 1, x + 1) <= path2(y + 1, x)) ret += count(y + 1, x);

	return ret;
}

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			//triangle[i][j] = 0;
			cache[i][j] = -1;
			countCache[i][j] = -1;
		}
	}
}
int main() {

	int tCase;
	cin >> tCase;
	while (tCase--) {
		cin >> n;
		init();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> triangle[i][j];
			}
		}
		cout << count(0, 0) << "\n";
	}

	return 0;
}