algospot - tripathcnt

//algospot - tripathcnt
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<vector<int>> tri;
vector<vector<int>> cache;
vector<vector<int>> cache2;
 
void init()
{
    cin >> N;
    tri = vector<vector<int>>(N, vector<int>(N));
    cache2 = cache = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<=i; ++j)
            cin >> tri[i][j];
}
 
int dp(int x, int y)
{
    if(x == N)
        return 0;
    int& ret = cache[x][y];
    if(ret != -1)
        return ret;
    ret = dp(x+1, y);
    ret = max(ret, dp(x+1, y+1));
    ret += tri[x][y];
    return ret;
}
 
int dp2(int x, int y)
{
    if(x == N-1)
        return 1;
    int& ret = cache2[x][y];
    if(ret != -1)
        return ret;
    ret = 0;
    if(cache[x+1][y] + tri[x][y] == cache[x][y])
        ret += dp2(x+1, y);
    if(cache[x+1][y+1] + tri[x][y] == cache[x][y])
        ret += dp2(x+1, y+1);
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        int max = dp(0,0);
        cout << dp2(0,0) << "\n";
    }
}

 

 

 

 

 

https://www.algospot.com/judge/problem/read/TRIPATHCNT

algospot.com :: TRIPATHCNT

 

 

 

 

 

TRIPATHCNT

경우의 수 DP문제

삼각형 위의 최대 경로를 DP로 구한다음 경로를 찾기 위해 DP를 한번 더 사용하면 됩니다!