[c++] 등굣길

#include <string>
#include <vector>
#define ll long long 
#define MOD 1000000007
using namespace std;
 
int dp[101][101];
int n,m;
 
int dfs(int y,int x){
    if(y == n && x == m) return 1; 
    
    if(y>n || x>m || dp[y][x]==-2) return 0;
 
    int &ret=dp[y][x];
    
    if(ret!=0)
        return ret;
    
    return ret=(dfs(y+1,x)%MOD+dfs(y,x+1)%MOD)%MOD;
}
 
 
int solution(int M, int N, vector<vector<int>> puddles) {
    int answer = 0;
    n=N;
    m=M;
    
    for(int i=0;i<puddles.size();i++){
        dp[puddles[i][1]][puddles[i][0]]=-2;
    }
    
    
    return dfs(1,1);
}
 
 

출처: https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

바텀업방식으로도 풀고 추가예정.
dp가 많이 미흡하네요