hardDynamic Programming 2DAI-applied~30 min
Count Strictly Increasing Paths on a Score Grid
On a grid of model confidence scores, count every strictly increasing walk (a monotone ascent of any length). Each single cell counts as a length-one path. Report the total modulo 1e9 + 7.
Problem
Given an m x n grid of integers, count the number of strictly increasing paths where you move to a 4-directionally adjacent cell with a strictly greater value. Paths of length 1 (a single cell) count too. Return the total number of such paths modulo 1e9 + 7.
Input
An m x n integer grid.
Output
An integer: the count of strictly increasing paths modulo 1e9 + 7.
Constraints
- 1 <= m, n <= 1000 with m * n <= 100000
- 1 <= grid[i][j] <= 10^5
Examples
Example 1
Input
grid = [[1,1],[3,4]]
Output
8
4 single cells plus paths 1->3, 1->4, 3->4, 1->3->4 = 8.
Example 2
Input
grid = [[1],[2]]
Output
3
Two single cells plus the path 1->2.