51. 最小路径和

RT

Scala标准集合库泛型版:

  // Time: O(m*n), Space: O(n)
  def minSumOfPath1dIterative[T: ClassTag](a: Iterable[Iterable[T]])(implicit nums: Numeric[T]): T = {
    val firstRow = a.head
    val d = firstRow.view.tail.scan(firstRow.head)(nums.plus).toArray
    for (row <- a.view.tail) {
      val colIter = row.iterator
      d(0) = nums.plus(d(0), colIter.next())
      for (c <- 1 until d.length) d(c) = nums.plus(nums.min(d(c), d(c - 1)), colIter.next())
    }
    d.last
  }

// scalatest
  test("tinSumOfPath1dIterative") {
    val matrix = Seq(IndexedSeq(1, 2, 1), List(8, 4, 1), Vector(-8, 2, 1))
    minSumOfPath1dIterative(matrix) should be(4)

    val matrix2: List[Seq[Double]] = List(IndexedSeq(1.2, 2.3, 1.2), Vector(8.9, 4.1, 1.2), Array(-8.2, 2.3, 1.5))
    minSumOfPath1dIterative(matrix2) should be(5.7)
  }