POJ1163The Triangle

1371 단어 
7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

전형적인 수탑 문제.
세 가지 솔루션:
1. 귀속.
2、DP
3. 기억화 검색
오늘은 동적 기획으로 이 입문 문제를 해결한다.
상태 전환 방정식:
dp[x][y] = max(dp[x+1][y],dp[x+1][y+1]) + maps[x][y];
동적 기획은 수학, 컴퓨터 과학과 경제학에서 사용되는 것으로 원문제를 상대적으로 간단한 자문제로 분해하는 방식으로 복잡한 문제를 풀 수 있는 방법이다.동적 기획은 중첩자 문제[1]와 최우수자 구조 성질의 문제에 자주 적용되고 소박한 해법보다 훨씬 적게 사용된다.
동적 기획 배후의 기본 사상은 매우 간단하다.대체적으로 주어진 문제를 풀려면 우리는 서로 다른 부분(즉 자문제)을 풀고 자문제의 해를 합쳐서 원문제의 해를 얻어야 한다.일반적으로 많은 하위 문제가 매우 비슷하다. 이를 위해 동적 기획법은 각 하위 문제를 한 번만 해결하여 계산량을 줄이려고 한다. 일단 하위 문제에 대한 해답이 계산되면 이를 기억화 저장하여 다음에 같은 하위 문제가 필요할 때 직접 표를 찾아볼 수 있도록 한다.이런 방법은 중복자 문제의 수가 수입의 규모가 지수적으로 증가할 때 특히 유용하다.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 105
int maps[MAX][MAX];
int dp[MAX][MAX];
int n;

void DP(int x, int y)
{
	for(int i = n - 1; i >= 1; i--)
	{
		for(int j = 1; j <= i; j++)
		{
			dp[i][j] = maps[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
		}
	}
}

int main()
{
	freopen("in.txt","r",stdin);
	int i, j;
	cin >> n;
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= i; j++)
		{
			cin >> maps[i][j];
		}
	}
	for(i = 1; i <= n; i++)
	{
		dp[n][i] = maps[n][i];
	}
	DP(1, 1);
	cout << dp[1][1] << endl;
}
Go의 포인터
동적 기획의 회문 최소 분할수

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage