🎮两种DP，一把神装
你，一位身披重甲的骑士，站在城堡的右下角（别问为什么不在正门，问就是策划设计的）。城堡的最深处——左上角，藏着一把传说中的武器：“全服第一·金光闪闪·一刀999·屠龙宝刀”。装备就是尊严，皮肤就是战力，这把刀要是落入别人手里，你在服务器里的排名就得从“榜一大哥”变成“榜外小弟”。
但这座城堡有个变态设定：每个房间要么堆着金币（数字 1~9），要么蹲着一只打呼噜的精英怪（障碍 X），而且你的重甲只允许三个移动方向——向上、向左、向左上角斜走。 向下？不存在的，骑士的尊严不允许走回头路，况且甲胄太重，下楼梯膝盖受不了。
你的目标非常清晰：
- 收集最多的金币——买不起屠龙宝刀的皮肤，你拿什么在队友面前装逼？
- 统计有多少种走法能刚好拿到这么多金币——万一队友问“你怎么来的”，你可以装作风轻云淡：“路线不多，也就几十种，我都算过了。”
如果根本走不到藏宝室……那就 [0, 0] 灰溜溜回城，看着世界频道刷屏：“恭喜玩家【隔壁剑圣】获得屠龙宝刀！”
动态规划双雄：一把刀，两种姿势
你站在起点，握紧了手中的剑。作为全服排名前三的骑士，你深知拿到这把刀的方式不止一种。今天，你打算用两种姿势征服这座城堡——先用商人的精算推演全局，再用猛男的头铁正面硬刚。一种姿势算胜负，两种姿势定乾坤。队友在语音里问：“你行不行啊？”你冷笑一声，回了两个字：“看号。”
姿势一：后向 DP——商人骑士的沙盘推演
“别急着往前冲，先想想终点在哪儿。”
你没有急着冲锋，而是把剑往地上一插，盘腿坐下，从背包里掏出一张泛黄的羊皮卷轴。卷轴封面写着四个字：“逆向演算”。
这个姿势的精髓是：假装你已经站在藏宝室门口了，然后倒着走回起点，沿途在每块地砖上记账。 定义 dp[i][j] = [maxGold, count]，意思是“从 (i,j) 出发走到藏宝室，最多能捞多少金币，以及有几条路能捞到这个数”。
藏宝室 E：你就站在终点，还没拔刀，口袋里零金币进账（
E本身不掉落），最大金币 = 0，方案数 = 1。精英怪房间 X：绕行，绕行！标记为不可达，金币 = -∞，方案数 = 0。谁拉怪谁负责，商人只打必赢的团。
普通金币房：你回头看——因为是倒着推，下一步其实是正向走法的“上一步”，也就是下方、右方、右下三个方向。扫一眼这三个邻居的账本，挑出
maxGold最大的那个，把方案数抄过来；如果有多个邻居并列最大，说明多条路都能让你捞到同样的最大金币，就把它们的方案数累加起来。然后，弯腰把当前房间地板缝里的金币（数字）抠出来加上——商人连一个铜板都不放过，这是职业素养。
当你倒推回起点 S 时，账本上赫然写着两个数字：最大金币数，和对应的路线方案数。如果最大金币还是 -∞，那说明连藏宝室的门都摸不到——不过全服前三的骑士，不存在这种情况。
def pathsWithMaxScore(board):
MOD = 10**9 + 7
n = len(board)
if board[n-1][n-1] == 'X' or board[0][0] == 'X':
return [0, 0]
# dp[i][j] = [max_score, count]
dp = [[[float('-inf'), 0] for _ in range(n)] for _ in range(n)]
dp[0][0] = [0, 1] # 站在藏宝室门口，不走路不捡钱，一种站姿
# 倒推的三个方向：下、右、右下
dirs = [(1, 0), (0, 1), (1, 1)]
for i in range(n):
for j in range(n):
if i == 0 and j == 0:
continue
if board[i][j] == 'X':
continue
max_score = float('-inf')
total_cnt = 0
for di, dj in dirs:
pi, pj = i - di, j - dj # 回头看是谁走过来的
if 0 <= pi < n and 0 <= pj < n and board[pi][pj] != 'X':
score, cnt = dp[pi][pj]
if score > max_score:
max_score = score
total_cnt = cnt
elif score == max_score:
total_cnt = (total_cnt + cnt) % MOD
if max_score != float('-inf'):
add = 0
if board[i][j] not in ('E', 'S'):
add = int(board[i][j])
dp[i][j] = [max_score + add, total_cnt]
res = dp[n-1][n-1]
return [res[0] if res[0] != float('-inf') else 0, res[1] % MOD]
你合上卷轴，拔出插在地上的剑。商人姿势的精髓在于：不动一刀一枪，胜负已在指尖。 队友在语音里沉默了——这哥们坐地上画了张图，就把路线全算完了？
姿势二：前向 DP——头铁猛男的正面碾压
“管他那么多，先冲再说！”
你把卷轴塞回背包，活动了一下肩胛骨，盔甲发出咔咔的金属摩擦声。“算完了？算完了就该开怪了。”
第二个姿势，是你最擅长的：正面冲锋，见一个房间踹一扇门，边跑边记。 这个姿势的哲学是：“路线是跑出来的，金币是捡出来的，骑士的功勋写在前胸，不在账本！”
定义 dp[i][j] = [maxGold, count]，意思是“从起点冲到这里，最多已经捞了多少金币，以及有几条路能捞到这个数”。
- 起点 S：你就站在这儿，还没开冲，口袋零金币，方案数 = 1——先原地吼一个 Buff，气势不能输。
- 精英怪房间 X：直接跳过！猛男虽然头铁，但还没铁到单挑睡着的精英怪——万一吵醒了团灭，队友要喷你。
- 普通金币房：你一脚踹开门，先看一眼是从哪个方向冲来的——因为正向只能向上、向左、向左上走，所以到达
(i,j)的上一个房间必然是它的上方、左方、左上方三个之一。从这三个方向里挑出maxGold最大的那个，把方案数搬过来（并列最大就累加）。然后低头一看，地板上有金币？弯腰，捡，一气呵成。动作快得像开了自动拾取，猛男捡钱从不墨迹。
当你一脚踹开藏宝室的大门时，口袋里的金币叮当乱响，手里的路线图已经被汗水和激情浸透。你低头一看——嘿，和刚才商人姿势算出来的数字一模一样！
def pathsWithMaxScore(board):
MOD = 10**9 + 7
n = len(board)
if board[n-1][n-1] == 'X' or board[0][0] == 'X':
return [0, 0]
dp = [[[float('-inf'), 0] for _ in range(n)] for _ in range(n)]
dp[n-1][n-1] = [0, 1] # 站在起点，还没冲，零金币，一种站姿
# 前推方向：上、左、左上
dirs = [(-1, 0), (0, -1), (-1, -1)]
for i in range(n-1, -1, -1):
for j in range(n-1, -1, -1):
if i == n-1 and j == n-1:
continue
if board[i][j] == 'X':
continue
max_score = float('-inf')
total_cnt = 0
for di, dj in dirs:
pi, pj = i - di, j - dj # 回头看：谁来的
if 0 <= pi < n and 0 <= pj < n and board[pi][pj] != 'X':
score, cnt = dp[pi][pj]
if score > max_score:
max_score = score
total_cnt = cnt
elif score == max_score:
total_cnt = (total_cnt + cnt) % MOD
if max_score != float('-inf'):
add = 0
if board[i][j] not in ('E', 'S'):
add = int(board[i][j])
dp[i][j] = [max_score + add, total_cnt]
res = dp[0][0]
return [res[0] if res[0] != float('-inf') else 0, res[1] % MOD]
你站在藏宝室中央，屠龙宝刀插在你面前的地砖里，金光把整个房间照得像开了 HDR。你的左手攥着金币袋，右手握着路线图，两个姿势给出的数字严丝合缝。
尾声：
你拔出屠龙宝刀，刀身发出嗡嗡的鸣响，世界频道弹出全服公告：
【系统公告】恭喜玩家“DP骑士”获得【屠龙宝刀】，服务器首杀！
队友在语音里炸了锅：“卧槽牛逼！你到底是算的还是莽的？”
你扛着刀走出城堡，眼眶微湿——因为宝刀的金光有点刺眼。你淡淡地回了句：“两种姿势，一种答案。双 DP 通关，不服来辩。”
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。