绝密Hut跑刀来

每个格子的值取决于上邻和左邻格子的和，而结果是单个格子的最大价值，可知最大值一定出现在右下角，只需先预处理最上一横行和最左一竖行的初始值再依次遍历更新每个格子的值，最后取右下角格子价值即可

参考代码（python）

from sys import stdin,setrecursionlimit
from math import inf,ceil,sqrt
from collections import Counter,deque

n=int(stdin.readline())
s=[[0 for _ in range(n)]for i in range(n)]
for i in range(n):
    s[0][i]=1
    s[i][0]=1
for i in range(1,n):
    for j in range(1,n):
        s[i][j]=s[i-1][j]+s[i][j-1]
print(s[n-1][n-1])