[C/C++]一級(BOJ)1932整数三角形

2346 ワード
ダイナミックプログラミング 白駿 C テキストリンク

質問の概要📌



質問リンク📢


https://www.acmicpc.net/problem/1932

問題を解く📝


整数三角形と最大のパスを求めます.筆者は経路を構築する際,各区間における合意最値を下から上への方法で更新した.
一度アクセスしたポイントは再更新する必要がないので、dpに値が存在する場合は、そのdp値を返し、再帰dpを使用します.dp[x][y] = max(triangle(x + 1, y), triangle(x + 1, y + 1)) + v[x][y];このように現在の場所を更新しました.
このようにして、下から上へ最大のパスを繰り返すことができます!

コード#コード#

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

vector <vector<int>> v;
vector <vector<int>> dp;
int N;
int triangle(int x, int y)
{
	if (x == N-1)
	{
		dp[x][y] = v[x][y];
		return v[x][y];
	}
	if (dp[x][y] == -1)
	{
		dp[x][y] = max(triangle(x + 1, y), triangle(x + 1, y + 1)) + v[x][y];
	}
	return dp[x][y];
}
int main()
{
	int num;
	vector <int> tmp1;
	vector <int> tmp2;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < i + 1; j++)
		{
			cin >> num;
			tmp1.push_back(num);
			tmp2.push_back(-1);
		}
		v.push_back(tmp1);
		dp.push_back(tmp2);
		tmp1.clear();
		tmp2.clear();
	}
	cout << triangle(0, 0);
	cout << dp[0][0];
	return 0;
}
Javaチームプロジェクト
Railsテスト『十』見逃せない雑多