Medium

题目描述

给定两个整数 n 和 k，以及两个二维整数数组 stayScore 和 travelScore。

一个游客正在访问一个有 n 个城市的国家，每个城市都与其他所有城市直接相连。游客的旅程恰好包含 k 天（从 0 开始索引），他们可以选择任意城市作为起点。

每一天，游客有两个选择：

  • 留在当前城市：如果游客在第 i 天留在当前城市 curr，他们将获得 stayScore[i][curr] 积分。
  • 移动到另一个城市：如果游客从当前城市 curr 移动到城市 dest，他们将获得 travelScore[curr][dest] 积分。

返回游客能够获得的最大积分。

示例 1：

输入：n = 2, k = 1, stayScore = [[2,3]], travelScore = [[0,2],[1,0]]
输出：3
解释：游客通过从城市 1 开始并留在该城市获得最大积分。

示例 2：

输入：n = 3, k = 2, stayScore = [[3,4,2],[2,1,2]], travelScore = [[0,2,1],[2,0,4],[3,2,0]]
输出：8
解释：游客通过从城市 1 开始，在第 0 天留在该城市，在第 1 天移动到城市 2 来获得最大积分。

约束条件：

  • 1 <= n <= 200
  • 1 <= k <= 200
  • n == travelScore.length == travelScore[i].length == stayScore[i].length
  • k == stayScore.length
  • 1 <= stayScore[i][j] <= 100
  • 0 <= travelScore[i][j] <= 100
  • travelScore[i][i] == 0

解题思路

这是一道典型的动态规划问题。我们需要找到游客在 k 天内能获得的最大积分。

核心思路： 定义状态 dp[i][j] 表示在第 i 天结束时，游客位于城市 j 能获得的最大积分。

状态转移： 对于第 i 天，游客在城市 j，有两种可能的来源：

  1. 从第 i-1 天就在城市 j，第 i 天选择留在原地：dp[i-1][j] + stayScore[i][j]
  2. 从第 i-1 天在其他城市 prev，第 i 天移动到城市 j：dp[i-1][prev] + travelScore[prev][j]

因此状态转移方程为：

dp[i][j] = max(
    dp[i-1][j] + stayScore[i][j],  // 留在原地
    max(dp[i-1][prev] + travelScore[prev][j])  // 从其他城市移动过来
)

优化空间： 由于只需要前一天的状态，可以使用一维数组进行空间优化。

时间复杂度分析：

  • 每一天需要计算所有城市的最大积分：O(n)
  • 每个城市需要考虑从所有其他城市移动过来：O(n)
  • 总共 k 天：O(k × n²)

代码实现

class Solution {
public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        vector<int> dp(n, 0);
        
        // 第0天，可以选择任意城市作为起点
        for (int j = 0; j < n; j++) {
            dp[j] = stayScore[0][j];
        }
        
        // 从第1天开始动态规划
        for (int i = 1; i < k; i++) {
            vector<int> newDp(n, 0);
            for (int j = 0; j < n; j++) {
                // 选择1：留在当前城市
                newDp[j] = dp[j] + stayScore[i][j];
                
                // 选择2：从其他城市移动过来
                for (int prev = 0; prev < n; prev++) {
                    if (prev != j) {
                        newDp[j] = max(newDp[j], dp[prev] + travelScore[prev][j]);
                    }
                }
            }
            dp = newDp;
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        # 初始化第0天的状态
        dp = [stayScore[0][j] for j in range(n)]
        
        # 从第1天开始动态规划
        for i in range(1, k):
            new_dp = [0] * n
            for j in range(n):
                # 选择1：留在当前城市
                new_dp[j] = dp[j] + stayScore[i][j]
                
                # 选择2：从其他城市移动过来
                for prev in range(n):
                    if prev != j:
                        new_dp[j] = max(new_dp[j], dp[prev] + travelScore[prev][j])
            
            dp = new_dp
        
        return max(dp)

public class Solution {
    public int MaxScore(int n, int k, int[][] stayScore, int[][] travelScore) {
        int[] dp = new int[n];
        
        // 第0天，可以选择任意城市作为起点
        for (int j = 0; j < n; j++) {
            dp[j] = stayScore[0][j];
        }
        
        // 从第1天开始动态规划
        for (int i = 1; i < k; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                // 选择1：留在当前城市
                newDp[j] = dp[j] + stayScore[i][j];
                
                // 选择2：从其他城市移动过来
                for (int prev = 0; prev < n; prev++) {
                    if (prev != j) {
                        newDp[j] = Math.Max(newDp[j], dp[prev] + travelScore[prev][j]);
                    }
                }
            }
            dp = newDp;
        }
        
        return dp.Max();
    }
}

var maxScore = function(n, k, stayScore, travelScore) {
    let dp = new Array(n);
    
    // 第0天，可以选择任意城市作为起点
    for (let j = 0; j < n; j++) {
        dp[j] = stayScore[0][j];
    }
    
    // 从第1天开始动态规划
    for (let i = 1; i < k; i++) {
        let newDp = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            // 选择1：留在当前城市
            newDp[j] = dp[j] + stayScore[i][j];
            
            // 选择2：从其他城市移动过来
            for (let prev = 0; prev < n; prev++) {
                if (prev !== j) {
                    newDp[j] = Math.max(newDp[j], dp[prev] + travelScore[prev][j]);
                }
            }
        }
        dp = newDp;
    }
    
    return Math.max(...dp);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k × n²) - k天，每天需要计算n个城市，每个城市需要考虑从n个城市转移
空间复杂度O(n) - 使用一维数组存储当前状态，空间优化后只需要O(n)空间