How would you solve the problem of unique paths in a grid using dynamic programming?

The problem of "unique paths in a grid" can be described as follows. We have an m x n grid, and we are situated at the top-left corner which is at coordinate (0, 0). We need to reach the bottom-right corner at coordinate (m-1, n-1). We are allowed to only move right or down. The problem is to calculate the total number of unique paths possible to reach the destination from the starting position.

This problem can be solved using dynamic programming (DP). In dynamic programming, we divide the problem into smaller subproblems, and we store the results of these subproblems. If we again encounter the same subproblem, we don’t have to solve it again; we can directly use the stored result.

Here’s how we can implement a solution using dynamic programming:

- We initialize a 2D array dp of size (m x n). Elements of dp represent the number of unique paths to that particular coordinate (i,j).

- We initialize the first row and the first column as 1, because there is only one way to reach any cell in the first row or first column i.e., by moving right or down only.

- Then we move towards the remaining cells (except the cells in the first row and first column). The number of ways to reach to a cell (i, j) would be the sum of number of ways to reach the cell (i, j-1) and the cell (i-1, j).

Here is how it can be expressed in code:

def uniquePaths(m, n):
    dp = [[1]*n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

Let’s take m=3 and n=7 for instance, the 2D dp array would look like this:

$$\begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 3 & 6 & 10 & 15 & 21 & 28 \end{array}$$

Time complexity of this solution is O(m*n) and space complexity is also O(m*n) as we are using an extra 2D DP table.

The last element dp[m-1][n-1] gives you the total unique paths from (0,0) to (m-1, n-1). In this case, that is 28 paths.