解法：Floyd 求最短路

本题使用到了 Floyd 求最短路算法。关于这个算法，我给力扣专栏写过一篇文章进行了详细的介绍，欢迎有兴趣的读者阅读：https://zhuanlan.zhihu.com/p/623757829

由于本题只能将单个字符改为其它字符，所以不同位置之间的修改互不影响，那么答案就是把 source[i] 改成 target[i] 的代价加起来，即 $\sum\limits_{i = 1}^n g(s_i, t_i)$，其中 $g(s_i, t_i)$ 是把字符 $s_i$ 改成 $t_i$ 的最小代价。

我们把每个字母看成一个点，如果能把字母 $x$ 改成字母 $y$，就从 $x$ 到 $y$ 连一条长度为 cost[i] 的有向边。这样对于任意两个字母 $x$ 和 $y$，把 $x$ 改成 $y$ 的最小代价就是从 $x$ 到 $y$ 的最短路。

由于我们需要知道任意两个点之间的最短路，所以可以使用 Floyd 算法。

复杂度 $\mathcal{O}(n + m + \Sigma^3)$，其中 $n$ 是 source 的长度，$m$ 是 original 的长度，$\Sigma$ 是字符集的大小，即 $26$。

参考代码（c++）

###c++

class Solution {
public:
    long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
        const int INF = 1e9;
        // 建有向图
        long long g[26][26];
        for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) g[i][j] = INF;
        for (int i = 0; i < 26; i++) g[i][i] = 0;
        for (int i = 0; i < original.size(); i++) {
            int x = original[i] - 'a', y = changed[i] - 'a';
            g[x][y] = min(g[x][y], 1LL * cost[i]);
        }

        // floyd 求最短路
        for (int k = 0; k < 26; k++) for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++)
            g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

        long long ans = 0;
        // 把每个位置的修改代价加起来
        for (int i = 0; i < source.size(); i++) {
            int x = source[i] - 'a', y = target[i] - 'a';
            if (x != y) {
                // x 不能变成 y，无解
                if (g[x][y] >= INF) return -1;
                // 否则答案增加把 x 改成 y 的最小代价
                ans += g[x][y];
            }
        }
        return ans;
    }
};

解法：DP

维护 $f(t, i, j)$ 表示经过 $t$ 次传送后走到 $(i, j)$ 的最小代价。转移方程如下：

1. 要么刚刚从一个更大数传送到 $(i, j)$，则 $f(t, i, j) \xleftarrow{\min} f(t - 1, i', j')$，其中 grd[i'][j'] >= grid[i][j]。
2. 要么通过普通移动走到 $(i, j)$，则 $f(t, i, j) \xleftarrow{\min} \min(f(t, i - 1, j), f(t, i, j - 1)) + a_{i, j}$。

需要注意两点：

1. 直接计算第一个转移方程的复杂度是 $\mathcal{O}((nm)^2)$ 的，我们可以将所有格子从大到小排序，这样就能用前缀 min 快速计算。
2. 第一个转移方程要在第二个转移方程之前计算，因为第二个转移方程可能会用到第一个转移方程的结果。

答案就是 $\min\limits_{0 \le t \le k} f(t, n - 1, m - 1)$，即枚举具体传送了几次。复杂度 $\mathcal{O}(nm\log nm + nmk)$。

参考代码（c++）

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int K) {
        int n = grid.size(), m = grid[0].size();

        const long long INF = 1e18;
        long long f[K + 1][n][m];
        for (int k = 0; k <= K; k++) for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) f[k][i][j] = INF;
        // 初值计算：不经过任何传送，走到 (i, j) 的最小代价
        f[0][0][0] = 0;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            if (i + 1 < n) f[0][i + 1][j] = min(f[0][i + 1][j], f[0][i][j] + grid[i + 1][j]);
            if (j + 1 < m) f[0][i][j + 1] = min(f[0][i][j + 1], f[0][i][j] + grid[i][j + 1]);
        }

        typedef pair<int, int> pii;
        // 把格子按值分类
        map<int, vector<pii>> mp;
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) mp[-grid[i][j]].push_back({i, j});
        // 枚举传送次数
        for (int k = 1; k <= K; k++) {
            long long mn = INF;
            // 计算第一个转移方程，按值从大到小枚举格子
            for (auto &p : mp) {
                // 更新前缀 min
                for (pii pos : p.second) mn = min(mn, f[k - 1][pos.first][pos.second]);
                for (pii pos : p.second) f[k][pos.first][pos.second] = mn;
            }
            // 计算第二个转移方程
            for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
                if (i > 0) f[k][i][j] = min(f[k][i][j], f[k][i - 1][j] + grid[i][j]);
                if (j > 0) f[k][i][j] = min(f[k][i][j], f[k][i][j - 1] + grid[i][j]);
            }
        }

        long long ans = INF;
        for (int k = 0; k <= K; k++) ans = min(ans, f[k][n - 1][m - 1]);
        return ans;
    }
};