Leetcode 1301: Number of Paths with Max Score

https://leetcode.com/problems/number-of-paths-with-max-score/description/

Notes:

This question is designed for dp, or dynamic programming. And it is not an easy question, as labeled as hard.

Let focus on the first step first: to find the maximum score.

Let dp[i][j] represents the maximum score when reaching the position board[i][j] from the bottom right corner.

Then we can derive the following state relations:

if board[i][j] >= '1' && board[i][j]<='9',  dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) + board[i][j] - '0';

if board[i][j] == 'S' or 'E', dp[i][j] = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) ;

if board[i][j] == 'X', dp[i][j] = -1;

Then there is a special case:  (no available previous steps...)

if(dp[i+1][j] == dp[i][j+1] == dp[i+1][j+1] == -1), dp[i][j] = -1;

After these, we still need to consider boundary condition.

if board[i][j] == 'X', and i==m-1, or j == n-1.

when i == m-1, we need to set dp[i+1][j] = -1; if j>0, dp[i+1][j-1] = -1;

when j == n-1, we need to set dp[i][j+1] = -1; if(i>0), dp[i-1][j+1] = -1;

(we can avoid the above boundary setting, if we set all dp values as -1 originally. Then we just need to set dp[m-1][n-1] = 0).

Okay, now we have finished the first step. So let move on to the second part.

If dp[0][0] < 0, meaning there is no path, we just return {0, 0}.

If not, we will use dfs (depth-first search) + memorization for the second part. The memorization is used to increase the time complexity.

Let memo[i][j] represents the number of ways reaching dp[i][j] from the bottom right corner.

Let set val = dp[i][j].

If(board[i][j] >='1' && board[i][j]<='9') we need to update the val -= board[i][j] - '0'.

Then memo[i][j] = (val==dp[i+1][j] ? memo[i+1][j] : 0) + (val==dp[i][j+1] ? memo[i][j+1] : 0) + (val==dp[i+1][j+1] ? memo[i+1][j+1] : 0).

One sentence summary: dp for the maximum score, then dfs + memo (or dp) for the first dp.

See the code below:

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int m = board.size(), n = board.front().size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=m-1; i>=0; --i) {
            for(int j=n-1; j>=0; --j) {
                if(dp[i+1][j] <0 && dp[i][j+1] <0 && dp[i+1][j+1] < 0 || board[i][j] == 'X') {
                    dp[i][j] = -1;
                    if(board[i][j] == 'X') {
                        if(i==m-1) {dp[i+1][j] = -1; if(j>0) dp[i+1][j-1] = -1;}
                        if(j==n-1) {dp[i][j+1] = -1; if(i>0) dp[i-1][j+1] = -1;}
                    }
                    continue;
                }
                dp[i][j] = max(max(dp[i+1][j], dp[i][j+1]), dp[i+1][j+1]);
                if(board[i][j] >= '1' && board[i][j] <='9') dp[i][j] += board[i][j] - '0';
            }
        }
        if(dp[0][0] < 0) return {0, 0};
        vector<vector<long>> memo(m+1, vector<long>(n+1, -1));
        int ways = dfs(0, 0, board, dp, memo);
        return {dp[0][0], ways};
    }

private:
    int cv = 1e9+7;
    int dfs(int i, int j, vector<string>& bs, vector<vector<int>>& dp, vector<vector<long>>& memo) {
        if(i+1==bs.size() && j+1 == bs.front().size()) return 1;
        if(i>=bs.size() || j>=bs.front().size()) return 0;
        if(memo[i][j] != - 1) return memo[i][j];
        int val = dp[i][j];
        if(bs[i][j]>='1' && bs[i][j] <='9') val -= bs[i][j] - '0';
        int a = 0, b = 0, c = 0;
        if(val == dp[i+1][j]) a = dfs(i+1, j, bs, dp, memo)% cv;
        if(val == dp[i][j+1]) b = dfs(i, j+1, bs, dp, memo)% cv;
        if(val == dp[i+1][j+1]) c = dfs(i+1, j+1, bs, dp, memo)%cv;
        return memo[i][j] = (a + b + c)%cv;
    }
};