Maximum weight path ending of last row in a matrix

Find the path having the maximum weight in integer matrix [N X M].

Conditions for moves:

Path should begin from top left element and can end at any element of last row. We can move to down (i+1, j) or diagonal forward (i+1, j+1).

public class MaxWeightPathMatrix {

    

     /**

      * Moves # down or forward diagonal.

      * @param matrix

      * @return Returns the maximum weight.

      */

     private static int getMaxWeightPath(int[][] matrix) {

           int row = matrix.length;

           int col = matrix[0].length;

           int[][] dp = newint[row][col];

           /** Initialize first row of total weight */

           for(inti=0;i<col;i++) {

                dp[0][i] = matrix[0][i];

           }

           /** Initialize first column of total weight */

           for (inti=1; i<row; i++) {

                dp[i][0] = matrix[i][0] + dp[i-1][0];

           }

           for(inti=1; i<row; i++) {

                for(intj=1; j<col; j++) {

                     dp[i][j] = matrix[i][j] + Math.max(dp[i-1][j],

                                dp[i-1][j-1]);

                }

           }

           /** Max weight path sum to rech the last row */

           int result = 0;

           for (inti=0; i<col; i++) {

                result = Math.max(dp[row-1][i], result);

           }

           return result;

     }

    

     /** Driver method. */

     public static void main(String[] args) {

          

           int[][] matrix = {{ 8, 4 ,6 ,8 ,2 },

                     { 4 , 18 ,2 ,20 ,10 },

                     {20, 2 ,6 , 0 ,40 },

                     {32 ,184, 82, 88 ,2},

                     {16, 302, 12, 8, 18}};

           int maxWeight = getMaxWeightPath(matrix);

           System.out.println("Maximum weight path ending at any"

                     + " element of last row in a matrix # "+ maxWeight);

     }

}