Giả sử chúng ta có một bảng hình vuông gồm các ký tự. Chúng ta có thể di chuyển trên bàn cờ bắt đầu từ ô vuông dưới cùng bên phải được đánh dấu bằng ký tự 'S'. Bây giờ chúng ta cần đến hình vuông trên cùng bên trái được đánh dấu bằng ký tự 'E'. Các ô vuông khác được dán nhãn bằng ký tự số từ 1 đến 9 hoặc có chướng ngại vật 'X'. Trong một lần di chuyển, chúng ta chỉ có thể đi lên, sang trái hoặc lên bên trái khi không có chướng ngại vật ở đó.
Chúng ta phải tìm danh sách hai số:số đầu tiên là tổng tối đa của các ký tự số mà chúng ta có thể thu thập và số thứ hai là số đường đi mà chúng ta có thể thực hiện để có được tổng lớn nhất đó. Đối với câu trả lời, hãy trả về nó theo mô-đun 10 ^ 9 + 7. Khi không có đường dẫn, hãy trả về [0, 0].
Vì vậy, nếu đầu vào là board =["E12", "1X1", "21S"], thì đầu ra sẽ là [1,2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=số hàng, m:=số cột
-
Xác định một mảng 3D có thứ tự n x m x 2
-
dp [n - 1, m - 1, 0] =0, dp [n - 1, m - 1, 1] =1
-
để khởi tạo i:=m - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
nếu b [n - 1, i] giống với ASCII của 'X' thì -
-
dp [n - 1, i, 0] =b [n - 1, i] - ASCII của '0' + dp [n - 1, i + 1, 0]
-
-
dp [n - 1, i, 1] + =dp [n - 1, i + 1, 1]
-
-
để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
nếu b [i, m - 1] giống với ASCII của 'X' thì -
-
dp [i, m - 1, 0] =b [i, m - 1] - ASCII của '0' + dp [i + 1, m - 1, 0]
-
-
dp [i, m - 1, 1] + =dp [i + 1, m - 1, 1]
-
-
để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
-
để khởi tạo j:=m - 2, khi j> =0, cập nhật (giảm j đi 1), thực hiện -
-
nếu b [i, j] giống với ASCII của 'X' thì -
-
dp [i, j, 0]:=(nếu b [i, j] giống ASCII của 'E' thì 0, ngược lại b [i, j] -ASCII của '0')
-
-
maxVal:=tối đa của {dp [i, j + 1, 0], dp [i + 1, j, 0], dp [i + 1, j + 1, 0]}
-
nếu maxVal giống 0 và (b [i + 1, j] không bằng ASCII của 'S' và b [i, j + 1] không bằng ASCII của 'S' và b [i + 1, j + 1] không bằng ASCII của 'S'), thì -
-
dp [i, j, 0]:=0
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
dp [i, j, 0]:=dp [i, j, 0] + maxVal
-
nếu dp [i + 1, j, 0] giống với maxVal thì -
-
dp [i, j, 1]:=dp [i, j, 1] + dp [i + 1, j, 1]
-
-
nếu dp [i + 1, j + 1, 0] giống với maxVal, thì -
-
dp [i, j, 1]:=dp [i, j, 1] + dp [i + 1, j + 1, 1]
-
-
nếu dp [i, j + 1, 0] giống với maxVal thì -
-
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
-
-
-
trả về dp [0, 0]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{"E12","1X1","21S"} Đầu ra
[1, 2, ]