#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/counting-principles/unique-paths-implementation-2

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/math-fundamentals/counting-principles/unique-paths-implementation-2

Repovive

Unique Paths - Implementation - Counting Principles | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Unique Paths - Implementation

(2D DP table)

Here's the full solution:


function uniquePaths(m, n)
    dp := 2D array of size m × n
    // Initialize first row and column
    for i from 0 to m - 1
        dp[i][0] := 1
    for j from 0 to n - 1
        dp[0][j] := 1
    // Fill the rest
    for i from 1 to m - 1
        for j from 1 to n - 1
            dp[i][j] := dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

You build up the table row by row. Each cell gets the sum of paths from above and from the left. Time: $O(m \times n)$ , Space: $O(m \times n)$ .