์๊ณ ๋ฆฌ์ฆ
- save[0][0] = 1 ๋ถํฐ ์์ํด์, ๋ชจ๋ ์ ์ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉฐ ์์ ์ ์, ์ผ์ชฝ ์ ๋ค ์ค ์์ ์๊ฒ๋ก ์ฌ ์ ์๋ ๋ชจ๋ ์ ๋ค์ save[i][j]์ ์ ์ฅํ๋ค.
์ฝ๋
#include <iostream>
typedef long long ll;
using namespace std;
int n, map[101][101];
ll save[101][101];
ll dp();
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
cout << dp();
}
ll dp() {
save[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int ki = i - 1; ki >= 0; ki--)
if (map[ki][j] == i - ki)
save[i][j] += save[ki][j];
for (int kj = j - 1; kj >= 0; kj--)
if (map[i][kj] == j - kj)
save[i][j] += save[i][kj];
}
}
return save[n - 1][n - 1];
}