题目描述

给你两个整数 n 和 k，和两个二维整数数组 stayScore 和 travelScore。

一位旅客正在一个有 n 座城市的国家旅游，每座城市都 直接 与其他所有城市相连。这位游客会旅游 恰好 k 天（下标从 0 开始），且旅客可以选择 任意 城市作为起点。

每一天，这位旅客都有两个选择：

• 留在当前城市：如果旅客在第 i 天停留在前一天所在的城市 curr，旅客会获得 stayScore[i][curr] 点数。
• 前往另外一座城市：如果旅客从城市 curr 前往城市 dest，旅客会获得 travelScore[curr][dest] 点数。

请你返回这位旅客可以获得的 最多 点数。

样例

输入：n = 2, k = 1,
stayScore = [[2,3]],
travelScore = [[0,2],[1,0]]

输出：3

解释：

旅客从城市 1 出发并停留在城市 1 可以得到最多点数。

输入：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，可以得到最多点数。

限制

• 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

算法

(动态规划) $O(kn^2)$

1. 设状态 $f(i, dest)$ 表示第 $i$ 天到达城市 $dest$ 可以得到最多的点数。$i$ 的有效下标从 $1$ 开始。
2. 初始时，$f(0, dest) = 0$，其余为 $-\infty$，也可以为 $0$（这是因为点数都是正的）。
3. 转移时，枚举上一天所在的城市 $src$，如果 $src \neq dest$，则转移 $f(i, dest) = \max(f(i, dest), f(i - 1, src) + travelScore(src, dest))$。否则，转移 $f(i, dest) = \max(f(i, dest), f(i - 1, src) + stayScore(i, dest))$。
4. 最终答案为 $\max(f(k, dest))$。

时间复杂度

• 动态规划的状态数为 $O(kn)$，转移时间为 $O(n)$，故总时间复杂度为 $O(kn^2)$。

空间复杂度

• 可以使用滚动数组优化掉第一维的状态表示，优化后的空间复杂度为 $O(n)$。

C++ 代码

const int N = 210;

class Solution {
private:
    int f[N], g[N];

    inline int max(int x, int y) {
        return x > y ? x : y;
    }

public:
    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {
        memset(f, 0, sizeof(f));

        for (int i = 1; i <= k; i++) {
            memset(g, 0, sizeof(g));

            for (int src = 0; src < n; src++)
                for (int dest = 0; dest < n; dest++)
                    if (src != dest)
                        g[dest] = max(g[dest], f[src] + travelScore[src][dest]);
                    else
                        g[dest] = max(g[dest], f[src] + stayScore[i - 1][dest]);

            memcpy(f, g, sizeof(f));
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[i]);

        return ans;
    }
};