算法动态规划

最优决策序列个数

字数统计: 2k字   |   阅读时长: 9分
,

摘要: 动态规划解决优化问题，求最优决策方案数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在动态规划的问题中，有时会遇到求某个具体的最优决策序列的问题，在 求具体的最优决策序列 中已经解决。

本文我们来看一下最优决策序列个数的问题。比较直接的办法是用一个额外的，与 dp 数组维度相同的数组 dp_cnt，记录从初态到各个状态的最优决策序列个数。

在推导 dp 的时候，当某个状态的所有决策均处理完成的时候，根据当前状态的最优决策转移到哪些状态，通过 dp_cnt 在那些状态的值来计算 dp_cnt 在当前状态的值。

也可以在推导完 dp 之后，再根据 dp 中的信息单独再推导 dp_cnt。

下面我们通过两个题来看一下具体的实现细节。

1301. 最大得分的路径数目

给你一个正方形字符数组 board ，你从数组最右下方的字符 ‘S’ 出发。

你的目标是到达数组最左上角的字符 ‘E’ ，数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。

一条路径的 「得分」 定义为：路径上所有数字的和。

请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。

如果没有任何路径可以到达终点，请返回 [0, 0] 。

提示：

1
2 <= board.length == board[i].length <= 100

示例 1：
输入：board = [“E23”,”2X2”,”12S”]
输出：[7,1]
示例 2：

输入：board = [“E12”,”1X1”,”21S”]
输出：[4,2]
示例 3：

输入：board = [“E11”,”XXX”,”11S”]
输出：[0,0]

算法：棋盘DP

首先写出动态规划算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义：
dp[i][j] := 从 (0, 0) 到 (i, j) 的最大和

答案：
dp[n - 1][m - 1]

初始化：
dp[0][0] = 0

状态转移：
dp[i][j] = board[i][j] + max(dp[i - 1][i - 1]
                            ,dp[i][j - 1]
                            ,dp[i - 1][j]
                            )
其中 i > 0, j > 0, board[i][j] 不是障碍

由于要求最优决策数，用一个额外的 dp_cnt 记录从初态到各个状态的最优决策数。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        const int MOD = 1e9 + 7;
        using ll = long long;
        int n = board.size();
        vector<vector<ll>> dp(n, vector<ll>(n, -1));
        dp[0][0] = 0;
        vector<vector<int>> cnts(n, vector<int>(n, 0));
        cnts[0][0] = 1;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j)
            {
                if(!check(board, i, j))
                    continue;

                int num = 0;
                if(board[i][j] >= '0' && board[i][j] <= '9')
                    num = board[i][j] - '0';

                // 处理当前状态的所哟可能决策
                if(i > 0 && j > 0 && dp[i - 1][j - 1] != -1)
                    dp[i][j] = max(dp[i][j], num + dp[i - 1][j - 1]);
                if(i > 0 && dp[i - 1][j] != -1)
                    dp[i][j] = max(dp[i][j], num + dp[i - 1][j]);
                if(j > 0 && dp[i][j - 1] != -1)
                    dp[i][j] = max(dp[i][j], num + dp[i][j - 1]);

                // 根据最优决策可以到达的状态对应的 dp_cnt 值，计算当前状态的 dp_cnt
                if(i > 0 && j > 0 && dp[i - 1][j - 1] != -1)
                    if(dp[i][j] == num + dp[i - 1][j - 1])
                        cnts[i][j] = (cnts[i][j] + (ll)cnts[i - 1][j - 1]) % MOD;
                if(i > 0 && dp[i - 1][j] != -1)
                    if(dp[i][j] == num + dp[i - 1][j])
                        cnts[i][j] = (cnts[i][j] + (ll)cnts[i - 1][j]) % MOD;
                if(j > 0 && dp[i][j - 1] != -1)
                    if(dp[i][j] == num + dp[i][j - 1])
                        cnts[i][j] = (cnts[i][j] + (ll)cnts[i][j - 1]) % MOD;
            }
        }
        if(dp[n - 1][n - 1] == -1)
            return {0, 0};
        return {(int)(dp[n - 1][n - 1] % MOD), cnts[n - 1][n - 1]};
    }

private:
    bool check(const vector<string>& board, int i, int j)
    {
        return board[i][j] != 'X';
    }
};

1976. 到达目的地的方案数

你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 1e9 + 7 取余 后返回。

提示：

1
2
3
4
5
6
7
8
1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= ui, vi <= n - 1
1 <= timei <= 1e9
ui != vi
任意两个路口之间至多有一条路。
从任意路口出发，你能够到达其他任意路口。

示例 1：
输入：n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出：4
解释：从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为：

  • 0 ➝ 6
  • 0 ➝ 4 ➝ 6
  • 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
  • 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

示例 2：
输入：n = 2, roads = [[1,0,10]]
输出：1
解释：只有一条从路口 0 到路口 1 的路，花费 10 分钟。

算法：动态规划 (Floyd)

参考文章 Floyd算法，写出动态规划算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义：
dp[i][j] = 从 i 到 j 的最短路径长度

初始化：
dp[i][j] = INF
dp[i][i] = 0
dp[i][j] = adj[i][j]，若 i, j 之间有边，且边权为 adj[i][j]

答案：
dp[0][n - 1]

状态转移
dp[i][j] = min(dp[i][k] + dp[k][j])

上述状态定义中，i 和 j 都是附加状态，k 才是阶段，代表当前考虑到了节点为 $0,1,\cdots,k-1$ 构成的子图。

因此在推导状态的时候，必须先枚举 k，然后再枚举 i，j。

推导完所有状态后，$dp[i][j]$ 表示的就是考虑了图中所有结点，从 i 到 j 的最短距离。

此时要考察从 s 到 t 的最短距离有多少种走法，记 dp_cnt[u] 表示从 u 到 t 的最优决策个数，从 u = s 开始，按照拓扑序依次推导 dp_cnt，具体推导方法如下：

若 adj[u][v] + dp[v][t] = dp[u][t]，那么从 u 出发，先经过一条边到 v 是一种可能的最优决策，这一路最终的方法数为 dp_cnt[v]，因此递归地推导 dp_cnt[v] 即可，直至 u = t。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
MOD = int(1e9 + 7)

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        INF = int(1e12)
        self.dp = [[INF  for _ in range(n)] for _ in range(n)]
        self.g = [[] for _ in range(n)]
        for s, t, w in roads:
            self.dp[s][t] = w
            self.dp[t][s] = w
            self.g[s].append((t, w))
            self.g[t].append((s, w))
        for i in range(n):
            self.dp[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    self.dp[i][j] = min(self.dp[i][j], self.dp[i][k] + self.dp[k][j])
        self.dp_cnt = [-1 for _ in range(n)]
        self.dp_cnt[n - 1] = 1
        return self.solve(0, n - 1)

    def solve(self, u, t):
        # 从 u 到 t，最短路径的条数
        if self.dp_cnt[u] != -1:
            return self.dp_cnt[u]
        self.dp_cnt[u] = 0
        for v, w in self.g[u]:
            if w + self.dp[v][t] == self.dp[u][t]:
                self.dp_cnt[u] = (self.dp_cnt[u] + self.solve(v, t)) % MOD
        return self.dp_cnt[u]
Share