Any suggestion on finding a standard tabulation way to solve this

Question

I have this question:

Given a grid of positive numbers, start from 0,0 and end at n,n. Move only to right and down. Find path with sum of numbers is maximum.

Input Example:

5 1 2

6 7 8

1 4 9

output Example: 35

I solved it with many scenarios for example i wrote an easy equation to get the max path length then take some decisions to get the correct result.

But this example is easy to got that it should solved using dynamic programming as it's recursion and some overlaps with small space:

                                       fn(0,0)
                            fn(0,1)            f(1,0)
                       f(0,2)    f(1,1)     f(2,0) f(1,1)

I solved it easy using Memoization technique:

       public int GetMaxPathTopDown(int r, int c, int[,] arr, int[,] mem)
    {
        if (r >= arr.GetLength(0) || c >= arr.GetLength(1))
        {
            return 0;
        }

        // Base Case
        if (r == arr.GetLength(0) - 1 && c == arr.GetLength(1) - 1)
        {
            return arr[r, c];
        }

        if (mem[r, c] != -1)
        {
            return mem[r, c];
        }

        int firstPath = GetMaxPathTopDown(r, c + 1, arr, mem);
        int secondPath = GetMaxPathTopDown(r + 1, c, arr, mem);
        return mem[r, c] = arr[r, c] + Math.Max(firstPath, secondPath);
    }

but I want to find standard solution to solve it using Tabulation way. I tried many solutions but i thought it's not a correct way of tabulation so any help?

Answer 1

The basic steps to build bottom-up dynamic programming solutions are as follows:

1- Determine the required set of parameters that uniquely describe the problem (the state).

2- If there are N parameters required to represent the states, prepare an N dimensional DP table, with one entry per state. This is equivalent to the memo table in top-down DP. However, there are differences. In bottom-up DP, we only need to initialize some cells of the DP table with known initial values (the base cases). Recall that in topdown DP, we initialize the memo table completely with dummy values (usually -1) to indicate that we have not yet computed the values.

3- Now, with the base-case cells/states in the DP table already filled, determine the cells/states that can be filled next (the transitions). Repeat this process until the DP table is complete. For the bottom-up DP, this part is usually accomplished through iterations, using loops. lets build a table for 3*3 array with values:

5 1 2
3 1 2
0 1 1

we notice that we need two parameters : Move_right, Move_down

initially, the first row and column should have the cumulative sum of the array elements to start maximization then follow the steps in the attached picture which explain the code below

dp[0,0] = arr[0,0];
for (int i = 1; i < n; i++){
    dp[0,i] = arr[0,i] + dp[0,i - 1];
}
for (int i = 1; i < n; i++){
    dp[i,0] = arr[i,0] + dp[i-1,0];
}

for (int i = 1; i < n; i++){
    for (int j = 1; j < n; j++){
        dp[i,j] = arr[i,j] + Math.max(dp[i - 1,j], dp[i,j - 1]);
    }
}

Console.WriteLine(dp[n - 1,n - 1]);

the required answer should be 12, and you find it in the most right-down cell building table

Answer 2

@Marzouk, you can try this:

dp[i, j] will be the maximum sum you can get from (0, 0) to (i, j). Now, dp[i, j] will depend on dp[i - 1, j] and dp[i, j - 1]. So, the recurrence will be:

dp[i, j] = max(dp[i - 1, j], dp[i, j - 1]) + mt[i, j]

You need to handle corner cases here (i = 0 or j = 0).

using System;

class MainClass {
  public static void Main (string[] args) {
    int[,] mt = new[,] { {5, 1, 2}, {6, 7, 8}, {1, 4, 9} };
    int[,] dp = new[,] { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} };

    int R = mt.GetLength(0);
    int C = mt.GetLength(1);
    for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++) {
        dp[i, j] = mt[i, j];
        if (i > 0 && j > 0) {
            dp[i, j] += Math.Max(dp[i - 1, j], dp[i, j - 1]);
        } else if (i > 0) {
            dp[i, j] += dp[i - 1, j];
        } else if (j > 0) {
            dp[i, j] += dp[i, j - 1];
        }
    }

    Console.WriteLine(dp[R-1, C-1]);
  }
}