Add Consecutive-Value Bonuses to Grid Paths

Problem Statement

You are given an m x n integer grid grid, and two non-negative integers eq_bonus and inc_bonus.

A robot starts at the top-left corner (0, 0) and must reach the bottom-right corner (m - 1, n - 1) by moving only Right ('R') or Down ('D') at each step.

Along any path of visited cells v[0], v[1], ..., v[k] (where k = m + n - 2 and v[i] is the integer value in the i-th visited cell):

• Base score: The sum of all visited cell values: sum(v[i]) for 0 = 1, if v[i] == v[i - 1], add eq_bonus to the score.
• Strictly increasing triple bonus: For every index i >= 2, if v[i] > v[i - 1] > v[i - 2], add inc_bonus to the score.

Compute:

1. The maximum total score achievable along any valid path.
2. The number of distinct valid paths that achieve this maximum score, modulo 10^9 + 7.
3. The lexicographically smallest path (represented as a string of 'D' and 'R') that achieves this maximum score. Note that 'D' is lexicographically smaller than 'R'.

Function Signature

def max_score_path(grid: list[list[int]], eq_bonus: int, inc_bonus: int) -> tuple[int, int, str]:
    """
    Returns (max_score, count_modulo, best_path_str).
    """
    pass

Constraints

• 1 <= m, n <= 100
• -10^4 <= grid[r][c] <= 10^4
• 0 <= eq_bonus, inc_bonus <= 10^4
• Modulo for path count: 1_000_000_007

Examples

Example 1

grid = [
    [1, 2],
    [2, 3]
]
eq_bonus = 5
inc_bonus = 10

max_score_path(grid, eq_bonus, inc_bonus)
# Output: (16, 2, "DR")

Explanation:

• Path "DR" visits (0, 0) -> (1, 0) -> (1, 1) with values [1, 2, 3]. Base score: 1 + 2 + 3 = 6. Equal bonus: 0. Increasing triple bonus: 1 (0, 1) -> (1, 1) with values [1, 2, 3]. Total score: 16.
• Both paths tie for the maximum score of 16. Total tied paths = 2. Between "DR" and "RD", "DR" is lexicographically smaller.

Example 2

grid = [
    [2, 2],
    [1, 2]
]
eq_bonus = 4
inc_bonus = 5

max_score_path(grid, eq_bonus, inc_bonus)
# Output: (14, 1, "RD")

Explanation:

• Path "RD" visits [2, 2, 2]. Base sum = 6. Adjacent equal bonuses at step 1 and step 2 give 4 + 4 = 8. Total score = 14.
• Path "DR" visits [2, 1, 2]. Base sum = 5, bonuses = 0. Total score = 5.
• Best score is 14, count is 1, path is "RD".