1890번: Jump The Board!

https://www.acmicpc.net/problem/1890

$O(n^2)$

dp[i][j]: (0,0)에서 (i,j)로 오는 경우의 수

#include<cstdio>
int n;
long long dp[109][109] = { 1 };
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) for (int j = 0; j < n; j++) {
        scanf("%d", &x);
        if (!x) continue;
        dp[i + x][j] += dp[i][j];
        dp[i][j + x] += dp[i][j];
    }
    printf("%lld", dp[n - 1][n - 1]);
    return 0;
}