Find path having maximum gold in matrix

Given a gold mine of n*m dimension. Each field in this mine contains an integer which is amount of gold in tons. Initially miner is in first column but could be at any row i. He can move only right, right up , right down. Find out maximum amount of gold he can collect.

Approach 1: Brute force

For every row find all possible paths and calculate the maximum gold. Find all the paths recursively and return maximum gold.

Approach 2: Dynamic Programming

During brute force approach we search same path multiple times, instead we can store the result and reuse the result for next iterations.

Code below implements approach 2.

class Solution {

    private static boolean isValidMove(int x, int y, int[][] matrix){
        if(x >= 0 && y >= 0){
            if(x < matrix.length && y < matrix[0].length ){
                return true;
            }
        }
        return false;
    }

    public static int findMaxGold(int[][] mines, int x, int y, int[][] storage){
        if(isValidMove(x, y, mines)){
            if(storage[x][y] != -1)
                return  storage[x][y];
            int rightGold = mines[x][y] + findMaxGold(mines, x, y+1, storage);
            int rightUpGold = mines[x][y] + findMaxGold(mines, x-1, y+1, storage);
            int rightDownGold = mines[x][y] + findMaxGold(mines, x+1, y+1, storage);
            int max = Math.max(rightGold, Math.max(rightDownGold, rightUpGold));
            storage[x][y] = max;
            return max;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] mines ={{1, 3, 5, 19},
                         {2, 5, 6, 8},
                         {9, 6, 6, 12},
                         {14, 2, 4, 22},
                         {0,  2, 4, 32}};
        int maxGold = Integer.MIN_VALUE;
        int[][] storage = new int [mines.length][mines[0].length];
        for (int i=0; i < storage.length; i++) {
            for(int j=0; j < storage[0].length;j++)
                storage[i][j] = -1;
        }

        for (int i=0; i < mines.length; i++){
            maxGold = Math.max(maxGold, findMaxGold(mines, i, 0, storage));
        }
        System.out.println("MAX Gold in Mine : " + maxGold);
    }
}