思路

• 状态：设 $dp[i][j]$ 为进入房间 $(i,j)$ 时已获得的最大价值。

• 转移（在网格内 $1 \le i,j \le n$）：

  

  

• 初值：$dp[1][1] = 0$（进入起点未拿任何宝藏）。

题目内容

有一座巨大的官殿，可以被视为由$n$行$n$列房间组成，从上到下分别为第$1,2,...n$行,从左到右分别为第$1,2,...n$列。第$i$行第$j$列房间内有价值为$a_{i,j}$的宝藏。

每个房间都有一扇通往下一行同一列的常开的门，即从第$i$行第$j$列房间能移动到第$i+1$行第$j$列房间，但是 如果选择带走房间内的宝藏，则该侧门会关闭。特别地，第$n$行的所有房间的通往下一行同一列的门都通往 宫殿外。