自动搬运

查看原文

来自洛谷，原作者为

	Naro_Ahgnay 值得就喜欢。

搬运于2025-08-24 22:31:48，当前版本为作者最后更新于2021-12-17 22:26:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个 $n \times n$ 的方格，只能从下或从右移动当前格子上的数那么多的步数，求出从左上角到右下角的方案数。

思路

对于求方案数的题目，不难发现这是一道 dp 题。状态转移方程也非常好推。

设 $dp[i][j]$ 表示现在在第 $i$ 行第 $j$ 列时的方案数，由题意得：

$\begin{Bmatrix}dp[i+g[i][j]][j]+=dp[i][j],i+g[i][j]≤n\\dp[i][j+g[i][j]]+=dp[i][j],j+g[i][j]≤n\end{Bmatrix}$

其中边界为 $dp[1][1]=1$,答案为 $dp[n][n]$。

但是，我们发现题目的数据范围极大，不得不用高精度。

于是——人生苦短，我用 python!

code

dp=[]
g=[]
for i in range(0,110):
    dp.append([])
    g.append([])
    for j in range(0,110):
        dp[i].append(0)
n=int(input())
for i in range(1,n+1):
    g[i]=input().split()
    g[i].append(int(g[i][n-1]))
    for j in range(n-1,0,-1):
        g[i][j]=int(g[i][j-1])
    
dp[1][1]=1
g[n][n]=1
for i in range(1,n+1):
    for j in range(1,n+1):
        if(i+g[i][j]<=n):
            dp[i+g[i][j]][j]+=dp[i][j]
        if(j+g[i][j]<=n):
            dp[i][j+g[i][j]]+=dp[i][j]
print(dp[n][n])