poj1163

동적 기획의 제목은 솔직히 동적 기획이 이해가 안 가요. 이 문제도 뇌가 다른 사람의 코드를 한 번 모의한 후에 이 방법을 배워서 마지막 층에서 수조로 결과를 보존하는 시간의 복잡도가 이전에 사용한 것보다 훨씬 작아요. o(n^2)만 있어요.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define M 101
int maxsum[M][M],D[M][M];
int n;
int Maxsum(int i,int j)
{
 if(maxsum[i][j]!=-1)
 return maxsum[i][j];
 if(i==n)
 maxsum[i][j]=D[i][j];
 else
 {
 int x=Maxsum(i+1,j);
 int y=Maxsum(i+1,j+1);
 maxsum[i][j]=max(x,y)+D[i][j];
 }
 return maxsum[i][j];
}