Two-Dimensional DP

Two-dimensional DP tracks two independent state parameters. We count monotone paths across an n-by-m grid, moving only right or down. Different step orders repeatedly reach the same cell, so a cell-indexed table captures the relevant history. The dependency picture makes row-major and column-major order easy to justify and prepares for string-prefix and knapsack tables.

Prerequisites: One-Dimensional DP; nested loops; coordinate indexing.

Build the idea

1. Recognize the repeated subproblems

   A route of n−1 down and m−1 right moves has many possible orders. Histories merge whenever they arrive at the same cell, because the future legal moves depend only on row and column. Constraints up to 1000 per dimension permit one million cells but not enumeration of all complete paths. The two indices describe location, not the entire route.

2. Define the state

   dp[r][c] is the number of paths from the top-left cell (0,0) to cell (r, c), modulo 10^9+7. Indices are zero-based internally, with 0≤r<n and 0≤c<m. No obstacles or weights occur in this introductory model. The pair is sufficient because remaining moves are determined entirely by the current location.

3. Derive the transition

   The final move into a nonstart cell is either down from (r−1, c) or right from (r, c−1). These are disjoint classes, so add valid predecessor counts. Missing above/left neighbors contribute zero. At the first row or first column only one predecessor exists, which automatically gives one route along each border.

   $$\mathrm{dp}\left[r\right]\left[c\right]=\mathrm{dp}[r-1]\left[c\right]+\mathrm{dp}\left[r\right][c-1]$$

4. Base cases and computation order

   Set dp[0][0]=1 for the empty movement sequence and skip reassigning that cell. Traverse rows top-to-bottom and columns left-to-right. Both above and left have been computed. Column-major traversal is also valid if columns increase outward and rows increase inside; reversing one direction may read a dependency too early.

5. Correctness and invariant

   Induct on r+c: all predecessors have smaller coordinate sum. Every route has one final edge and is counted once in exactly one predecessor class. Thus the cell sum is correct, including the borders. The same argument fails if arbitrary up/left movement is allowed, because dependencies can cycle and even the number of unrestricted walks may be infinite.

6. Work the example

   For three rows and four columns, the table ends at 10. Row zero is all ones; row one becomes 1,2,3,4; row two becomes 1,3,6,10. The final cell combines 4 from above with 6 from the left. The table is a visualization of the recurrence, not a separate algorithm.

   row / col	0	1	2	3
   0	1	1	1	1
   1	1	2	3	4
   2	1	3	6	10

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n,m;
    std::cin>>n>>m;
    std::vector<std::vector<int>>dp(n,std::vector<int>(m));
    dp[0][0]=1;
    for(int r=0;r<n;++r){
        for(int c=0;c<m;++c){
            if(r==0&&c==0){
                continue;
            }
            long long ways=0;
            if(r){
                ways+=dp[r-1][c];
            }
            if(c){
                ways+=dp[r][c-1];
            }
            dp[r][c]=ways%1000000007;
        } // Only up/left dependencies, corresponding to down/right moves.
    }
    std::cout<<dp[n-1][m-1]<<'\n';
}

Complexity analysis

nm states, at most two constant-time transitions: O(nm) time and O(nm) table space. A rolling row reduces DP memory to O(m), or O(min(n, m)) after rotating this symmetric obstacle-free problem.

Example input and output

Read n m with 1≤n, m≤1000. Allowed moves are right/down between grid cells; print paths from top-left to bottom-right modulo 10^9+7.

Input

3 4

Output

10

For three rows and four columns, the table ends at 10. Row zero is all ones; row one becomes 1,2,3,4; row two becomes 1,3,6,10. The final cell combines 4 from above with 6 from the left. The table is a visualization of the recurrence, not a separate algorithm.

Practical applications

Use two-dimensional states when two independent pieces of information affect future choices, such as two string prefixes or an item layer plus capacity. The Grid DP lesson adds obstacles and costs without changing the allowed movement DAG.

Check your understanding

Which property permits both row-major and column-major forward orders?

Put it into practice

Fill a 3-by-3 table by hand in both orders.