Algorithm Class - Matrix Path Problem 2

Seojun is working as a teaching assistant for a dynamic programming class again today. Let us check through a problem whether the students understood what his father taught in class.

An n × n matrix m of positive integers is given. Starting at the top left of the matrix, you move one cell at a time to reach the bottom right. The sum of the numbers in the cells you visit along the way is the score of that path. The movement rules are as follows.

• You can move only to the right or downward.
• Moving left, up, or diagonally is not allowed.

The pseudocode for the matrix path problem, which finds the highest score among all paths from (1, 1) to (n, n) in the matrix, is given below. Let us check how much faster dynamic programming is than recursive calls. Given the matrix size n and the matrix m, output the execution counts of Code 1 and Code 2.

The recursive pseudocode for the matrix path problem is as follows.

matrix_path(m[][], n) {  # Find the highest score from (1, 1) to (n, n).
    return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) {  # Find the highest score from (1, 1) to (i, j).
    if (i == 0 or j == 0) then
        return 0; # Code 1
    else
        return (mij + (max(matrix_path(m, i-1, j), matrix_path(m, i, j-1))));
}

The dynamic programming pseudocode for the matrix path problem is as follows.

matrix_path(m[][], n) {  # Find the highest score from (1, 1) to (n, n).
    for i <- 0 to n
        d[i, 0] <- 0;
    for j <- 1 to n
        d[0, j] <- 0;
    for i <- 1 to n
        for j <- 1 to n
            d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]);  # Code 2
    return d[n, n];
}

The first line gives the size of the matrix, n (5 ≤ n ≤ 1,000).

The next n lines each contain n integers representing one row of the matrix, separated by single spaces. Each cell value is between 1 and 100,000 inclusive.

Output the execution counts of Code 1 and Code 2 modulo 1,000,000,007 on one line.