1520 내리막길

dp(i,j) : (i,j)에서 시작해서 끝(m-1, n-1)까지 가는 경로의 합

dp(i,j) = 인접칸 y,x(네 방향)의 dp(y,x)들의 합 (arr[i][j] > arr[y][x] 인 경우에만) 

#include <iostream>

#include <memory.h>

using namespace std;

int m,n,arr[501][501],cache[501][501];

int func(int y, int x)

{

if(y==m-1 && x == n-1) return 1;

if(y>m-1 || x>n-1 || y<0 || x<0) return 0;

int &ret = cache[y][x];

if(ret != -1) return ret;

int std = arr[y][x], count=0;

//위 아 왼 오

if(y>0 && std > arr[y-1][x]) count+=func(y-1,x);

if(y<m-1 && std > arr[y+1][x]) count+=func(y+1,x);

if(x>0 && std > arr[y][x-1]) count+=func(y,x-1);

if(x<n-1 && std > arr[y][x+1]) count+=func(y,x+1);

return ret = count;

}

int main() {

cin>>m>>n;

for(int i=0;i<m; i++)for(int j=0;j<n;j++)cin>>arr[i][j];

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

cout<<func(0,0);

return 0;

}