60. Unique paths

60_solution1_mixed.c

#include <stdlib.h>

int uniquePaths(int m, int n) {
  int *dp = calloc(m * n, sizeof(int)); // dp[i * n + j]: paths from (i, j)
  dp[(m - 1) * n + (n - 1)] = 1;

  for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      if (i == m - 1 && j == n - 1)
        continue;
      int down = (i + 1 < m) ? dp[(i + 1) * n + j] : 0;
      int right = (j + 1 < n) ? dp[i * n + (j + 1)] : 0;
      dp[i * n + j] = down + right;
    }
  }
  int res = dp[0];
  free(dp);
  return res;
}

60_solution2_optmzd.c

#include <stdlib.h>

int uniquePaths(int m, int n) {
  int *dp = malloc(n * sizeof(int));
  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];
  int res = dp[n - 1];
  free(dp);
  return res;
}

60_solution3_memo.c

#include <stdlib.h>

static int solve(int i, int j, int n, int *dp) {
  if (i == 0 && j == 0)
    return 1; // reached the start
  if (i < 0 || j < 0)
    return 0; // fell off the grid
  if (dp[i * n + j] != -1)
    return dp[i * n + j]; // already computed

  int up = solve(i - 1, j, n, dp);
  int left = solve(i, j - 1, n, dp);
  return dp[i * n + j] = up + left;
}

int uniquePaths(int m, int n) {
  int *dp = malloc(m * n * sizeof(int)); // dp[i * n + j]
  for (int k = 0; k < m * n; k++)
    dp[k] = -1;
  int res = solve(m - 1, n - 1, n, dp);
  free(dp);
  return res;
}

60_solution4_tab.c

#include <stdlib.h>

int uniquePaths(int m, int n) {
  int *dp = calloc(m * n, sizeof(int)); // dp[i * n + j]

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (i == 0 && j == 0) {
        dp[0] = 1;
        continue;
      }
      int up = (i > 0) ? dp[(i - 1) * n + j] : 0;
      int left = (j > 0) ? dp[i * n + (j - 1)] : 0;
      dp[i * n + j] = up + left;
    }
  }
  int res = dp[(m - 1) * n + (n - 1)];
  free(dp);
  return res;
}

60_solution1_mixed.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[m - 1][n - 1] = 1;

    for (int i = m - 1; i >= 0; i--) {
      for (int j = n - 1; j >= 0; j--) {
        if (i == m - 1 && j == n - 1)
          continue;
        int down = (i + 1 < m) ? dp[i + 1][j] : 0;
        int right = (j + 1 < n) ? dp[i][j + 1] : 0;
        dp[i][j] = down + right;
      }
    }
    return dp[0][0];
  }
};

60_solution2_optmzd.cpp

#include <vector>

using namespace std;

class Solution {
public:
  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];
  }
};

60_solution3_memo.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int solve(int i, int j, vector<vector<int>> &dp) {
    if (i == 0 && j == 0)
      return 1; // reached the start
    if (i < 0 || j < 0)
      return 0; // fell off the grid
    if (dp[i][j] != -1)
      return dp[i][j]; // already computed

    int up = solve(i - 1, j, dp);
    int left = solve(i, j - 1, dp);
    return dp[i][j] = up + left;
  }

  int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, -1));
    return solve(m - 1, n - 1, dp);
  }
};

60_solution4_tab.cpp

#include <vector>

using namespace std;

class Solution {
public:
  int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (i == 0 && j == 0) {
          dp[i][j] = 1;
          continue;
        }
        int up = (i > 0) ? dp[i - 1][j] : 0;
        int left = (j > 0) ? dp[i][j - 1] : 0;
        dp[i][j] = up + left;
      }
    }
    return dp[m - 1][n - 1];
  }
};

60_solution1_mixed.go

package dp

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[m-1][n-1] = 1

    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if i == m-1 && j == n-1 {
                continue
            }
            down, right := 0, 0
            if i+1 < m {
                down = dp[i+1][j]
            }
            if j+1 < n {
                right = dp[i][j+1]
            }
            dp[i][j] = down + right
        }
    }
    return dp[0][0]
}

60_solution2_optmzd.go

package dp

func uniquePaths(m int, n int) int {
    dp := make([]int, n)
    for j := range dp {
        dp[j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[j] += dp[j-1]
        }
    }
    return dp[n-1]
}

60_solution3_memo.go

package dp

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var solve func(i, j int) int
    solve = func(i, j int) int {
        if i == 0 && j == 0 {
            return 1 // reached the start
        }
        if i < 0 || j < 0 {
            return 0 // fell off the grid
        }
        if dp[i][j] != -1 {
            return dp[i][j] // already computed
        }

        up := solve(i-1, j)
        left := solve(i, j-1)
        dp[i][j] = up + left
        return dp[i][j]
    }

    return solve(m-1, n-1)
}

60_solution4_tab.go

package dp

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                dp[i][j] = 1
                continue
            }
            up, left := 0, 0
            if i > 0 {
                up = dp[i-1][j]
            }
            if j > 0 {
                left = dp[i][j-1]
            }
            dp[i][j] = up + left
        }
    }
    return dp[m-1][n-1]
}

60_solution1_mixed.java

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[m - 1][n - 1] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1)
                    continue;
                int down = (i + 1 < m) ? dp[i + 1][j] : 0;
                int right = (j + 1 < n) ? dp[i][j + 1] : 0;
                dp[i][j] = down + right;
            }
        }
        return dp[0][0];
    }
}

60_solution2_optmzd.java

import java.util.Arrays;

class Solution {
    public 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];
    }
}

60_solution3_memo.java

import java.util.Arrays;

class Solution {
    private int solve(int i, int j, int[][] dp) {
        if (i == 0 && j == 0)
            return 1; // reached the start
        if (i < 0 || j < 0)
            return 0; // fell off the grid
        if (dp[i][j] != -1)
            return dp[i][j]; // already computed

        int up = solve(i - 1, j, dp);
        int left = solve(i, j - 1, dp);
        return dp[i][j] = up + left;
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int[] row : dp)
            Arrays.fill(row, -1);
        return solve(m - 1, n - 1, dp);
    }
}

60_solution4_tab.java

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                int up = (i > 0) ? dp[i - 1][j] : 0;
                int left = (j > 0) ? dp[i][j - 1] : 0;
                dp[i][j] = up + left;
            }
        }
        return dp[m - 1][n - 1];
    }
}

60_solution1_mixed.js

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[m - 1][n - 1] = 1;

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      if (i === m - 1 && j === n - 1) continue;
      const down = i + 1 < m ? dp[i + 1][j] : 0;
      const right = j + 1 < n ? dp[i][j + 1] : 0;
      dp[i][j] = down + right;
    }
  }
  return dp[0][0];
};

60_solution2_optmzd.js

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (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];
};

60_solution3_memo.js

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(-1));

  const solve = (i, j) => {
    if (i === 0 && j === 0) return 1; // reached the start
    if (i < 0 || j < 0) return 0; // fell off the grid
    if (dp[i][j] !== -1) return dp[i][j]; // already computed

    const up = solve(i - 1, j);
    const left = solve(i, j - 1);
    return (dp[i][j] = up + left);
  };

  return solve(m - 1, n - 1);
};

60_solution4_tab.js

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) {
        dp[i][j] = 1;
        continue;
      }
      const up = i > 0 ? dp[i - 1][j] : 0;
      const left = j > 0 ? dp[i][j - 1] : 0;
      dp[i][j] = up + left;
    }
  }
  return dp[m - 1][n - 1];
};

60_solution1_mixed.py

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        dp[m - 1][n - 1] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i == m - 1 and j == n - 1:
                    continue
                down = dp[i + 1][j] if i + 1 < m else 0
                right = dp[i][j + 1] if j + 1 < n else 0
                dp[i][j] = down + right
        return dp[0][0]

60_solution2_optmzd.py

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[n - 1]

60_solution3_memo.py

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[-1] * n for _ in range(m)]

        def solve(i: int, j: int) -> int:
            if i == 0 and j == 0:
                return 1  # reached the start
            if i < 0 or j < 0:
                return 0  # fell off the grid
            if dp[i][j] != -1:
                return dp[i][j]  # already computed

            up = solve(i - 1, j)
            left = solve(i, j - 1)
            dp[i][j] = up + left
            return dp[i][j]

        return solve(m - 1, n - 1)

60_solution4_tab.py

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = 1
                    continue
                up = dp[i - 1][j] if i > 0 else 0
                left = dp[i][j - 1] if j > 0 else 0
                dp[i][j] = up + left
        return dp[m - 1][n - 1]

60_solution1_mixed.rs

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![vec![0; n]; m];
        dp[m - 1][n - 1] = 1;

        for i in (0..m).rev() {
            for j in (0..n).rev() {
                if i == m - 1 && j == n - 1 {
                    continue;
                }
                let down = if i + 1 < m { dp[i + 1][j] } else { 0 };
                let right = if j + 1 < n { dp[i][j + 1] } else { 0 };
                dp[i][j] = down + right;
            }
        }
        dp[0][0]
    }
}

60_solution2_optmzd.rs

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![1; n];
        for _ in 1..m {
            for j in 1..n {
                dp[j] += dp[j - 1];
            }
        }
        dp[n - 1]
    }
}

60_solution3_memo.rs

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let mut dp = vec![vec![-1; n as usize]; m as usize];
        Self::solve(m - 1, n - 1, &mut dp)
    }

    // i, j are i32 so they can step below 0 without underflow
    fn solve(i: i32, j: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
        if i == 0 && j == 0 {
            return 1; // reached the start
        }
        if i < 0 || j < 0 {
            return 0; // fell off the grid
        }
        let (r, c) = (i as usize, j as usize);
        if dp[r][c] != -1 {
            return dp[r][c]; // already computed
        }

        let up = Self::solve(i - 1, j, dp);
        let left = Self::solve(i, j - 1, dp);
        dp[r][c] = up + left;
        dp[r][c]
    }
}

60_solution4_tab.rs

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![vec![0; n]; m];

        for i in 0..m {
            for j in 0..n {
                if i == 0 && j == 0 {
                    dp[i][j] = 1;
                    continue;
                }
                let up = if i > 0 { dp[i - 1][j] } else { 0 };
                let left = if j > 0 { dp[i][j - 1] } else { 0 };
                dp[i][j] = up + left;
            }
        }
        dp[m - 1][n - 1]
    }
}