Min Cost in maze traversal - LeetCode 62 : Unique Paths

 

package pep.Day17;

import java.util.HashMap;
import java.util.Map;

public class LeetCode_62_Unique_Paths {

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7));

    }


    public static int uniquePaths(int m, int n) {
        int[][] maze = new int[m][n];

        //return recursion(0,0,m-1, n-1);

        int[][] dp = new int[m + 1][n + 1];

        //return recursionMemo(0,0,m-1, n-1, dp);

        return recursionTabulation(0, 0, m - 1, n - 1, dp);

    }

    public static int recursion(int sr, int sc, int dr, int dc) {
        if (sr == dr && sc == dc)
            return 1;
        int[][] dirns = {{1, 0}, {0, 1}};

        int pathCount = 0;

        for (int[] dir : dirns) {
            int x = sr + dir[0];
            int y = sc + dir[1];

            if (x <= dr && y <= dc) {
                pathCount += recursion(x, y, dr, dc);
            }

        }

        return pathCount;
    }

    public static int recursionMemo(int sr, int sc, int dr, int dc, int[][] dp) {
        if (sr == dr && sc == dc)
            return dp[sr][sc] = 1;

        if (dp[sr][sc] != 0) return dp[sr][sc];

        int[][] dirns = {{1, 0}, {0, 1}};

        int pathCount = 0;

        for (int[] dir : dirns) {
            int x = sr + dir[0];
            int y = sc + dir[1];

            if (x <= dr && y <= dc) {
                pathCount += recursionMemo(x, y, dr, dc, dp);
            }

        }

        return dp[sr][sc] = pathCount;
    }

    public static int recursionTabulation(int SR, int SC, int dr, int dc, int[][] dp) {
        for (int sr = dr; sr >= SR; sr--) {

            for (int sc = dc; sc >= SC; sc--) {

                if (sr == dr && sc == dc) {
                    dp[sr][sc] = 1;
                    continue;
                }

                //if(dp[sr][sc] != 0) return dp[sr][sc];

                int[][] dirns = {{1, 0}, {0, 1}};

                int pathCount = 0;

                for (int[] dir : dirns) {
                    int x = sr + dir[0];
                    int y = sc + dir[1];

                    if (x <= dr && y <= dc) {
                        pathCount += dp[x][y]; //recursionTabulation(x, y, dr, dc, dp);
                    }

                }

                dp[sr][sc] = pathCount;
            }
        }

        return dp[SR][SC];

    }
}