백준 1520 내리막길

문제

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

문제 설명

dp를 이용한 문제 좌측 상단에서 우하단까지 갈 수 있는 경우를 다 구하면된다
지나갈때마다 다음의 위치는 현재위치보다 작아야한다

주의

• 기저조건에서 x == 1, y == 1일때 return 1로 가야한다

• base조건을 넣어줄때 그것을 생략하니 withdoutReturn도 나고 -38이라는 값도 발생하였다 이부분에서 왜 -가 나오지 싶었는데 초기화가 -1로 되어있는데 밑에 for문을 타면서 dp[x][y] += 과정에서 -1이 누적된 것같다

• 그리고 dp top -down에서는 항상 함수 마지막에 return을 하는 습관을 가지는 것이 실수를 줄여준다

소스

#include <bits/stdc++.h>

using namespace std;

//dp[i][j] -> i, j에 왔을때 가능한 경우의 수 
int a[501][501];
int dp[501][501];
int n, m;

//상 하 좌 우로 이동 가능 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

int solve(int x, int y) {

    //기저 
    if (x == 1 && y == 1) return 1;

    if (dp[x][y] != -1) return dp[x][y];

    //엥?
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;

        //check 처음에 >로 진행했다 
        if (a[x][y] >= a[nx][ny]) continue;

        dp[x][y] += solve(nx, ny) ;
    }
    //마지막으로 return 달아주자 
    return dp[x][y];
}
int main() {


    memset(dp, -1, sizeof(dp));

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    cout << solve(n, m) << endl;

    return 0;
}