資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++ 中具有最大分數的路徑數
假設我們有一個字元的方形棋盤。我們可以從標記為字元“S”的右下角方格開始在棋盤上移動。現在我們需要到達標記為字元“E”的左上角方格。其他方格用數字字元 1 到 9 或障礙物“X”標記。一步之內，我們只能向上、向左或左上移動，前提是沒有障礙物。
我們必須找到兩個數字的列表：第一個數字是我們能收集到的數字字元的最大和，第二個數字是可以採取的獲得該最大和的路徑數。對於答案，將其返回模 10^9 + 7。如果沒有路徑，則返回 [0, 0]。
因此，如果輸入類似於 board = ["E12","1X1","21S"]，則輸出將為 [1,2]
為了解決這個問題，我們將遵循以下步驟：
n := 行數，m := 列數
定義一個 3D 陣列，階數為 n x m x 2
dp[n - 1, m - 1, 0] = 0, dp[n - 1, m - 1, 1] = 1
對於初始化 i := m - 2，當 i >= 0 時，更新（i 減 1），執行：
如果 b[n - 1, i] 與 'X' 的 ASCII 碼相同，則：
dp[n - 1, i, 0] = b[n - 1, i] - '0' 的 ASCII 碼 + dp[n - 1, i + 1, 0]
dp[n - 1, i, 1] += dp[n - 1, i + 1, 1]
對於初始化 i := n - 2，當 i >= 0 時，更新（i 減 1），執行：
如果 b[i, m - 1] 與 'X' 的 ASCII 碼相同，則：
dp[i, m - 1, 0] = b[i, m - 1] - '0' 的 ASCII 碼 + dp[i + 1, m - 1, 0]
dp[i, m - 1, 1] += dp[i + 1, m - 1, 1]
對於初始化 i := n - 2，當 i >= 0 時，更新（i 減 1），執行：
對於初始化 j := m - 2，當 j >= 0 時，更新（j 減 1），執行：
如果 b[i, j] 與 'X' 的 ASCII 碼相同，則：
dp[i, j, 0] := (如果 b[i, j] 與 'E' 的 ASCII 碼相同，則為 0，否則為 b[i, j] - '0' 的 ASCII 碼)
maxVal := {dp[i, j + 1, 0], dp[i + 1, j, 0], dp[i + 1, j + 1, 0]} 的最大值
如果 maxVal 等於 0 並且 (b[i + 1, j] 不等於 'S' 的 ASCII 碼並且 b[i, j + 1] 不等於 'S' 的 ASCII 碼並且 b[i + 1, j + 1] 不等於 'S' 的 ASCII 碼)，則：
dp[i, j, 0] := 0
忽略以下部分，跳到下一次迭代
dp[i, j, 0] := dp[i, j, 0] + maxVal
如果 dp[i + 1, j, 0] 等於 maxVal，則：
dp[i, j, 1] := dp[i, j, 1] + dp[i + 1, j, 1]
如果 dp[i + 1, j + 1, 0] 等於 maxVal，則：
dp[i, j, 1] := dp[i, j, 1] + dp[i + 1, j + 1, 1]
如果 dp[i, j + 1, 0] 等於 maxVal，則：
dp[i, j, 1] := dp[i, j, 1] + dp[i, j + 1, 1]
dp[i, j, 1] := dp[i, j, 1] mod m
dp[i, j, 0] := dp[i, j, 0] mod m
返回 dp[0, 0]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
} cout << "]"<<endl;
}
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
return ((a % m) + (b % m) % m);
} class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& b) {
int n = b.size();
int m = b[0].size();
vector < vector < vector <int> > > dp(n, vector < vector
<int> >(m, vector <int> (2)));
dp[n - 1][m - 1][0] = 0;
dp[n - 1][m - 1][1] = 1;
for(int i = m - 2; i >= 0; i--){
if(b[n - 1][i] == 'X')break;
dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1]
[0];
dp[n - 1][i][1] += dp[n - 1][i + 1][1];
}
for(int i = n - 2; i >= 0; i--){
if(b[i][m - 1] == 'X')break;
dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1]
[0];
dp[i][m - 1][1] += dp[i + 1][m - 1][1];
}
for(int i = n - 2; i >= 0; i--){
for(int j = m - 2; j >= 0; j--){
if(b[i][j] == 'X')continue;
dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0';
int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0],
dp[i + 1][j + 1][0]});
if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] !
= 'S' && b[i+1][j + 1] != 'S')){
dp[i][j][0] = 0;
continue;
}
dp[i][j][0] += maxVal;
if(dp[i + 1][j][0] == maxVal){
dp[i][j][1] += dp[i + 1][j][1];
}
if(dp[i + 1][j + 1][0] == maxVal){
dp[i][j][1] += dp[i + 1][j + 1][1];
}
if(dp[i][j + 1][0] == maxVal){
dp[i][j][1] += dp[i][j + 1][1];
}
dp[i][j][1] %= m;
dp[i][j][0] %= m;
}
}
return dp[0][0];
}
};
main(){
Solution ob;
vector<string> v = {"E12","1X1","21S"};
print_vector(ob.pathsWithMaxScore(v));
}輸入
{"E12","1X1","21S"}輸出
[1, 2, ]
瀏覽量 143 次
