Starting from first row/col in dynamic programming (Longest Common Subsequence)

121

Hello, today I was trying to solve Longest Common Subsequence (1143) using dynamic programming. The solution starts to iterate the dp array in reverse order. But why doesn't it work if I simply start from the beginning?

Here is my code:

class Solution {
    /* Dynamic programming with tabulation */

    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        for (int r = 1; r < text1.length(); r++) {
            for (int c = 1; c < text2.length(); c++) {
                if (text1.charAt(r - 1) == text2.charAt(c - 1))
                    dp[r][c] = 1 + dp[r - 1][c - 1];
                else
                    dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1]);
            }
        }

        return dp[text1.length() - 1][text2.length() - 1];
    }
}

But it's giving wrong answer. And here is the solution code which traverses in reverse:

class Solution {
    
  public int longestCommonSubsequence(String text1, String text2) {    
    
    // Make a grid of 0's with text2.length() + 1 columns 
    // and text1.length() + 1 rows.
    int[][] dpGrid = new int[text1.length() + 1][text2.length() + 1];
        
    // Iterate up each column, starting from the last one.
    for (int col = text2.length() - 1; col >= 0; col--) {
      for (int row = text1.length() - 1; row >= 0; row--) {
        // If the corresponding characters for this cell are the same...
        if (text1.charAt(row) == text2.charAt(col)) {
          dpGrid[row][col] = 1 + dpGrid[row + 1][col + 1];
        // Otherwise they must be different...
        } else {
          dpGrid[row][col] = Math.max(dpGrid[row + 1][col], dpGrid[row][col + 1]);
        }
      }
    }
        
    // The original problem's answer is in dp_grid[0][0]. Return it.
    return dpGrid[0][0];
  }
}

Can someone explain me why my solution won't work, and why traversing from reverse direction works?

Comments (3)