https://www.acmicpc.net/problem/1890
initial
I thought of DFS + DP. But I think my implementation is printing too much values
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
dp[0][0] = 1
def dfs(i, j):
if i == n - 1 and j == n - 1:
return dp[-1][-1]
if dp[i][j] != 0:
return dp[i][j]
val = graph[i][j]
# down
if 0 < i + val < n:
dp[i + val][j] = max(dp[i + val][j], dp[i][j] + val)
dfs(i + val, j)
# right
if 0 < j + val < n:
dp[i][j + val] = max(dp[i][j + val], dp[i][j] + val)
dfs(i, j + val)
for i in range(n):
for j in range(n):
dfs(i, j)
print(dp[-1][-1])solution
with just dp. We initialise the starting point with value 1 that is gonna be used to be incremented to next down and right grids. Since all other grids are 0, if starting grid has value 2, then the grid right beside it will just have dp value of 0 whereas grid 2 positions to the right will have value 1. This initialising helps carry the number of ways to traverse that grid forward until the [-1][-1] grid.
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(n)] for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(n):
if i == n - 1 and j == n - 1:
print(dp[-1][-1])
exit() # Exit the program when the result is found
val = graph[i][j]
# down
if 0 < i + val < n:
dp[i + val][j] += dp[i][j]
# right
if 0 < j + val < n:
dp[i][j + val] +=dp[i][j]complexity
n^2 time and space
