Imagine a robot sitting on the upper left hand corner of an n xx n grid $($in the point $(0,0)).$ The robot can only move in three directions: right, down and diagonally down. The robot has to reach the lower right hand corner of the n xx n grid $($the point $($n$,$n$)).$ Your goal is to determine the number of possible paths for the robot.

Solve this problem using dynamic programming approach. Figure out:

$($a$)(4$ points$)$ What a subproblem is$.$

$($b$)(8$ points$)$ What the relation between subproblems $($recurrence$)$ is$.$

$($c$)(4$ points$)$ What the base cases are.

$($d$)(4$ points$)$ How the original problem is related to the subproblems.