最优决策序列个数

  |  

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

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


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

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

在推导 dp 的时候,当某个状态的所有决策均处理完成的时候,根据当前状态的最优决策转移到哪些状态,通过 dp_cnt 在那些状态的值来计算 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';
}
};

Share