[백준] 1520번 내리막 길 (DFS + DP)

-문제

 

 

 

-코드

#include<stdio.h>
using namespace std;

int n, m;
int map[501][501], dp[501][501];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int DFS(int x, int y)
{
	int xx, yy;
	if (x == n && y == m) return 1;
	if (dp[x][y] != -1) return dp[x][y];
	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		xx = x + dx[i];
		yy = y + dy[i];
		if (xx<1 || xx>n || yy<1 || yy>m) continue;
		if (map[xx][yy] < map[x][y]) 
		{
			dp[x][y] += DFS(xx, yy);
		}
	}
	return dp[x][y];
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &map[i][j]);
			dp[i][j] = -1;
		}
	}
	printf("%d\n", DFS(1, 1));
	return 0;
}