백준 1932 정수삼각형 c++ // 재귀dp, 1,2,3,4..n 개 입력받는법

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

 

1. 1,2,3,4..n 개 입력받는법

int n; cin >> n;
	for (int i = 1; i <= n; i++) { //높이
		for (int j = 1; j <= i; j++) { //가로
			cin >> dp[i][j];
		}
	}

j<=i 하면 되네???

 

2. 의사코드

1. 아래, 우아래 로 이동 하는 dfs

2. 그때 상태를 dp에저장 : 그상태일때 최대값

3. 기저사례1 : 정상적으로 n번째 노드에 노착

기저사례2 : x가 아래 그림과같이 빨간x쳐진곳으로 간경우 -> 비정상 -> 매우작은값을리턴시켜 배제시킴.

                     - 특징발견 : x>y인 경우가 그러함.

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

int n,m,a[504][504];
int dp[504][504];

//상태 : 좌표 : 그때 합 최대값
int dfs(int y, int x) {
    if (y >= n) {
        return 0;
    }
    if (x > y) { //정상경로가 아닌경우 배제
        return -1e9;
    }
    if (dp[y][x]!=-1) return dp[y][x];

    dp[y][x] = 0;
    dp[y][x] = max(dfs(y + 1, x)+a[y+1][x], dfs(y + 1, x + 1) + a[y + 1][x+1]);

    return dp[y][x];
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    m = 1;
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m && m<=n; ++j) {
            cin >> a[i][j];
        }
        m++;
    }

   /* for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << a[i][j] << " ";
        }cout << "\n";
    }*/

    cout << dfs(0, 0) + a[0][0];

    return 0;

}