Unique Paths to the Bottom-Right Corner

Problem

Starting from the top-left corner, what is the number of possible unique paths to reach the bottom-right corner, if you can only move either down or right at any point in time?

Dynamic Programming Solution for Moving Down/Right

#dynamic-programming

The number of unique paths to grid[r][c] is the number of unique paths to grid[r-1][c] plus the number of unique paths to grid[r][c-1], e.g.,

At any given time, we’re interested in two adjacent rows, so our space usage should be at most \(2n\). Furthermore, we do not back-track to the left, so if we update our values left-to-right, we can use \(n\) space because the current cell will have the value from what would have been in the previous row.

int uniquePaths(int m, int n) {
  if (m <= 0 || n <= 0) return 0;

  std::vector<int> numPathsToPosition(n, 0);
  numPathsToPosition[0] = 1;

  for (int r = 0; r < m; ++r) {
    for (int c = 0; c < n; ++c) {
      if (int nextC = c + 1; nextC < n) {
          numPathsToPosition[nextC] += numPathsToPosition[c];
      }
    }
  }

  return numPathsToPosition[n-1];
}

The above solution is pretty fast for ’s online judge, so the runtime (less than 5ms) is not comparable. The runtime is \(O(m n)\).

The memory usage is \(O(n)\). Per , that’s \(\approx\) 6MB which is better than 63% of submissions. The range is 5,400 KB to 6,500 KB, so all submissions within an order of magnitude of each other.

Combinatorics Solution for Moving Down/Right

#combinatorics

models the problem as a combinatorics problem: to get to the bottom-right, we need to choose \(m - 1\) right moves and \(n - 1\) down moves, from a total of \(m + n - 2\) moves.

$$ C_{m-1}^{m+n-2} = C_{n-1}^{m+n-2} = \frac{(m+n-2)!}{(m-1)!(n-1)!} $$

Assuming \(m > n\) in order to eliminate \((m-1)!\) gives us:

$$ C_{m-1}^{m+n-2} = \frac{(m+n-2) \times (m+n-3) \times … \times (m+n-n) \times (m-1) \times … \times 1 }{ ((m-1) \times (m-2) \times … \times 1) (n-1)!} $$ $$ = \frac{(m+n-2) \times (m+n-3) \times … \times m}{(n-1)!} $$

int unique_paths(int m, int n) {
  long num_combinations = 1;
  const int m_prime = max(m, n);
  // Because m' > n', when `num <= m'` all of the values in [1, n') will
  // have been visited by the loop.
  for (int num = m + n - 2, denom = 1; num >= m_prime; --num, ++denom) {
    num_combinations *= num;
    if (denom < n) num_combinations /= denom;
  }
  return num_combinations;
}

Re-ordering \(m, n\), such that \(m\) is the max, the loop goes through \(m + n - 2 - m = n - 2\) iterations, and therefore the runtime is \(O(min(m, n))\). The space usage is \(O(1)\). I don’t think we can do better than this.

Takeaways

I was wrong to earlier assume that because other people’s solutions were within one magnitude of 6MB, the DP solution was the optimal one. Sometimes \(n\) is too small to distinguish between optimal and sub-optimal solutions.

The regularity of the problem (well-defined grid; only moving right/down) should hint at a (probably optimal) math-based answer.

References

1. Unique Paths (Medium) - LeetCode. leetcode.com . leetcode.com . leetcode.com . Accessed Jul 30, 2022.
2. Fundamental types - cppreference.com. en.cppreference.com . Accessed Jul 30, 2022.
3. Fixed width integer types (since C++11) - cppreference.com. en.cppreference.com . Accessed Jul 30, 2022.
4. ✅ [C++/Python] 5 Simple Solutions w/ Explanation | Optimization from Brute-Force to DP to Math - LeetCode Discuss. leetcode.com . Accessed Jul 30, 2022.
5. elementary number theory - Proof that a Combination is an integer - Mathematics Stack Exchange. math.stackexchange.com . Accessed Jul 31, 2022.
6. Binomial Coefficient is Integer - ProofWiki. proofwiki.org . Accessed Jul 31, 2022.
7. Factorial Divides Product of Successive Numbers - ProofWiki. proofwiki.org . Accessed Jul 31, 2022.
8. std::numeric_limits - cppreference.com. en.cppreference.com . en.cppreference.com . Accessed Jul 31, 2022.