[백준 14494] 다이나믹이 뭐예요?

 

너무 쉬운 dp문제이긴 한데, dp문제는 모두 포스팅하기로 정해서 올린다.

 

문제에 써있는대로 탑다운 방식으로 풀었다.

n, m에서 왼쪽, 왼쪽위, 위 방향으로 이동하면서 1, 1에 도착했을때의 개수를 더해주었다.

 

public class Main {
    
    static long dp[][];
    
    public static long dp(int n, int m) {
        if(n == 0 || m == 0) return 0;
        if(n == 1 && m == 1) return 1;
        if(dp[n][m] != -1) return dp[n][m];
        
        long result = (dp(n, m-1) + dp(n-1, m) + dp(n-1, m-1))%1000000007;
        dp[n][m] = result;
        return result;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        dp = new long[n+1][m+1];
        for(int i=0; i<=n; i++)
            for(int j=0; j<=m; j++)
                dp[i][j] = -1;
        
        System.out.println(dp(n, m)%1000000007);
    }
}