Unique Paths

Medium Dynamic Programming

Count the number of paths from the top-left to the bottom-right of an m x n grid, moving only right or down. One-row DP.

Sample input

m = 3, n = 7

Sample output

Solution

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

print(unique_paths(3, 7))

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
}

console.log(uniquePaths(3, 7));

import java.util.Arrays;

public class Main {
    static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }

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

fun uniquePaths(m: Int, n: Int): Int {
    val dp = IntArray(n) { 1 }
    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[j] += dp[j - 1]
        }
    }
    return dp[n - 1]
}

fun main() {
    println(uniquePaths(3, 7))
}

func uniquePaths(_ m: Int, _ n: Int) -> Int {
    var dp = [Int](repeating: 1, count: n)
    if m > 1 && n > 1 {
        for _ in 1..<m {
            for j in 1..<n {
                dp[j] += dp[j - 1]
            }
        }
    }
    return dp[n - 1]
}

print(uniquePaths(3, 7))

int uniquePaths(int m, int n) {
  final dp = List.filled(n, 1);
  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }
  return dp[n - 1];
}

void main() {
  print(uniquePaths(3, 7));
}

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

int main() {
    cout << uniquePaths(3, 7) << endl;
    return 0;
}

#include <stdio.h>

int uniquePaths(int m, int n) {
    int dp[100];
    for (int j = 0; j < n; j++) dp[j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

int main() {
    printf("%d\n", uniquePaths(3, 7));
    return 0;
}