In Java!!!

A rat is located at the top-left corner of a M N grid A. M 1, N 1. It can only move either down or right at any point in time. The rat is trying to reach the bottom-right corner of the grid. How many possible unique paths are there? For example, if M = 2, N = 2, there are two possible unique paths: A[0][0] A[0][1] A[1][1], A[0][0] A[1][0] A[1][1].

(a) Based on the recurrence relation, give a naive recursive way to solve this problem

(b) Use dynamic programming to solve this problem

(c) Now consider there are some obstacles in the grid A, the rat can not go through the obstacles. An obstacle and empty space is marked as 1 and 0 respectively. How many unique paths?