3332. 旅客可以得到的最多点数（Rating 1827）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

3332. 旅客可以得到的最多点数

Rating 1827

思路

动态规划。

考虑：如果已知第i天在第x个城市的点数，那么第i+1天去往第y个城市的点数如何求解

代码

class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        dp = [[0 for _ in range(n)] for _ in range(k + 1)] # 二维dp，第一维是天数（为了方便边界处理，这里天数从1开始），第二维是城市编号
        for i in range(1, k + 1): # 遍历天数
            for x in range(n): # 遍历当前城市
                for y in range(n): # 遍历之前所在的城市
                    if x == y: # 如果当前城市和之前所在的城市相同，则表示停留在了该城市一天，获得对应的stayScore
                        dp[i][x] = max(dp[i][x], dp[i - 1][y] + stayScore[i - 1][x])
                    else: # 否则，获得从y到x的travelScore
                        dp[i][x] = max(dp[i][x], dp[i - 1][y] + travelScore[y][x])
        return max(dp[-1]) # 最后看下走完所有天后最后停留在哪个城市的点数最大，获得最大点数