76. 路径数量

RT

Scala:

  // Time: O(m*n), Space: O(m*n)
  def uniquePathsDP(m: Int, n: Int): Int = {
    val d = Array.fill(m, n)(1)
    for {
      i <- 1 until m
      j <- 1 until n
    } d(i)(j) = d(i)(j - 1) + d(i - 1)(j)

    d(m - 1)(n - 1)
  }

  // Time: O(min(m, n)), Space: O(1)
  def uniquePathsMath(m: Int, n: Int): Int = {
    val small = math.min(m - 1, n - 1)
    val total = m + n - 2
    (0 until small)
      .foldLeft(1L) { (result, i) =>
        result * (total - i) / (i + 1)
      }
      .toInt
  }

Test:

  "Unique Paths" should {
    "dp" in { uniquePathsDP(2, 4) shouldBe 4 }
    "math" in { uniquePathsMath(2, 4) shouldBe 4 }
  }