POJ 1163: Triangle(동적 계획)
3145 단어 POJ
단순 동태 기획, 사고방식: 표 작성
#include
#include
using namespace std;
const int maxSize = 105;
int n;
int arr[maxSize][maxSize];
int d[maxSize][maxSize];
void readInput(int n) //
{
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
cin >> arr[i][j];
}
void showInput(int n) //
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
cout << d[i][j];
cout << "
";
}
}
int maxSum(int i, int j)
{
if (n == i) return 0; // , 0
if (d[i][j] >= 0) return d[i][j]; // 0, ,
return d[i][j] = arr[i][j] + max(maxSum(i+1,j), maxSum(i+1,j+1)); //
}
int main()
{
while (cin >> n)
{
memset(d, -1, sizeof(d)); // -1
readInput(n);
cout << maxSum(0, 0) << endl;
//showInput(n);
}
return 0;
}