Variant 3 of 16.3 (Dynamic Programming)

#1

Elements of Programming in Java

Problem 16.3 - Count the number of ways to traverse a 2D array.

Variant 3: A fisherman is in a rectangular sea. The value at the fish at point (i,j) in the sea is specified by an nxm matrix. Write a program that computes the maximum value of fish a fisherman can catch on a path from the upper leftmost to lower rightmost points. The fisherman can only move right or down.

My initial approach was recursive. Recursively see all valid paths and sum all the values of fish along the path. Once the fisherman reaches top left (starting from bottom right), add the sum to a list and later extract maximum from the list to display the answer. The code below implements this algorithm.

//calculate max fish caught in grid
public static int maxFishInGrid(int[][] sea) {
    int maxFish = 0;
    ArrayList<Integer> result = new ArrayList<>();  
    computeFish(sea, sea.length-1, sea[0].length-1, 0, result);
    for(int a: result) {
        maxFish = Math.max(maxFish, a);
    }
    return maxFish;
}

private static void computeFish(int[][] sea, int i, int j, int sum, ArrayList<Integer> result) {   
    if(i == 0 && j == 0) {
        result.add(sum+sea[i][j]);
        return;
    }
    sum += sea[i][j];
    if(i > 0 ) {
        computeFish(sea, i-1, j, sum, result);
    }
    if(j > 0) {
        computeFish(sea, i, j-1, sum, result);
    }
}

My question is how can I memoize the results to make this a DP solution.

0 Likes
#2

I would suggest simplifying the task by first solving memoization. When that’s done, you’ll be in a better position to tackle making the solution DP.

0 Likes
#3

Isn’t memoization itself DP?

0 Likes
#4

@wolfBlade True. But it seems often when people say “DP”, they mean specifically solutions that are memoized, bottom-up, and non-recursive.

0 Likes