2025-05-21：旅客可以得到的最多点数。用go语言，有一个国家包含 n 座城市，城市之间全部直接相连。一位游客计划游玩恰好 k 天（天数编号从0开始），起点城市可自由选择。

每天游客有两种行动方案：

1. 留在当前城市：第 i 天停留在当天所在城市 curr，可获得 stayScore[i][curr] 的积分。

2. 前往其他城市：从当前城市 curr 出发，访问另一城市 dest，可获得 travelScore[curr][dest] 的积分。

请你计算游客在这 k 天内能获得的最高总积分。

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。

输入：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 ，第 1 天前往城市 2 ，可以得到最多点数。

题目来自力扣3332。

动态规划思路

1. 状态定义：

   • 定义 f[i][j] 表示从第 i 天开始游玩，当前位于城市 j 时，能够获得的最大积分。
   • 目标是计算 f[0][j] 的最大值（即从第 0 天开始，可以选择任意起点城市）。

2. 初始化：

   • 由于游玩天数是 k 天（编号从 0 到 k-1），所以 f[k][j] 表示第 k 天（即游玩结束后）的积分，此时没有任何积分可以获取，因此 f[k][j] = 0。

3. 状态转移：

   • 对于第 i 天（i 从 k-1 到 0 逆序计算）：
     • 如果选择留在当前城市 j，则积分为 stayScore[i][j] + f[i+1][j]。
     • 如果选择从城市 j 前往城市 dest，则积分为 travelScore[j][dest] + f[i+1][dest]。
     • f[i][j] 取上述两种选择的最大值。

4. 最终结果：

   • 最大总积分为 max(f[0][j] for all j)，即从第 0 天开始，选择任意起点城市的最大积分。

时间和空间复杂度

• 时间复杂度：
  • 外层循环是 k 天（从 k-1 到 0），内层循环是 n 个城市，对于每个城市需要比较 n 个可能的移动选择。
  • 总时间复杂度为 O(k * n^2)。
• 空间复杂度：
  • 使用了一个 (k+1) x n 的二维数组 f。
  • 总空间复杂度为 O(k * n)。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func maxScore(n, k int, stayScore, travelScore [][]int) int {
	f := make([][]int, k+1)
	f[k] = make([]int, n)
	for i, row := range slices.Backward(stayScore) {
		f[i] = make([]int, n)
		for j, s := range row {
			f[i][j] = f[i+1][j] + s // s=stayScore[i][j]
			for d, ts := range travelScore[j] {
				f[i][j] = max(f[i][j], f[i+1][d]+ts)
			}
		}
	}
	return slices.Max(f[0])
}

func main() {
	n := 3
	k := 2
	stayScore := [][]int{{3, 4, 2}, {2, 1, 2}}
	travelScore := [][]int{{0, 2, 1}, {2, 0, 4}, {3, 2, 0}}
	result := maxScore(n, k, stayScore, travelScore)
	fmt.Println(result)
}

Rust完整代码如下：

fn max_score(n: usize, k: usize, stay_score: &Vec<Vec<i32>>, travel_score: &Vec<Vec<i32>>) -> i32 {
    // f[i][j] 表示第 i 天，停留在城市 j 时，可以获得的最高总分
    let mut f = vec![vec![0; n]; k + 1];

    // 从第 k 天开始（k 是天数总数，实际上是结束状态，所有分数为0）
    // 反向计算，天数从 k-1 到 0
    for i in (0..k).rev() {
        for j in 0..n {
            // 留在当前城市 j
            let mut max_points = stay_score[i][j] + f[i + 1][j];
            // 选择去其他城市 dest
            for dest in 0..n {
                let points = travel_score[j][dest] + f[i + 1][dest];
                if points > max_points {
                    max_points = points;
                }
            }
            f[i][j] = max_points;
        }
    }

    // 起点城市可以自由选择，返回第 0 天所有城市的最大值
    *f[0].iter().max().unwrap()
}

fn main() {
    let n = 3;
    let k = 2;
    let stay_score = vec![vec![3, 4, 2], vec![2, 1, 2]];
    let travel_score = vec![vec![0, 2, 1], vec![2, 0, 4], vec![3, 2, 0]];

    let result = max_score(n, k, &stay_score, &travel_score);
    println!("{}", result);
}