地图和动态规划更新

Question

我得到的问题是

一个孩子正在跑一个有 n 级台阶的楼梯，并且一次可以跳 1 级、2 级或 3 级。实施一种方法来计算孩子可以通过多少种可能的方式跑上楼梯。

http://play.golang.org/p/bpjIkMm9jH

package main

import "fmt"

func CountWaysDP(n int, mm map[int]int) int {

  if n < 0 {

    return 0

  } else if n == 0 {

    return 1

  } else if mm[n] > -1 {

    return mm[n]

  } else {

    mm[n] = CountWaysDP(n-1, mm) +

      CountWaysDP(n-2, mm) +

      CountWaysDP(n-3, mm)

    return mm[n]

  }

}

func main() {

  mm := make(map[int]int)

  fmt.Println(CountWaysDP(10, mm), mm)

}

这只是给了我 0 地图 []。事实证明，动态递归在以下行结束：

else if mm[n] > -1

那么我将如何使用动态规划来解决这个问题呢？这与破解编码面试中的解决方案完全相同......

Answer 1

您需要与 0 进行比较：else if mm[n] > 0获取不存在的键的值时，map 返回 0。您也可以使用数组/切片而不是映射，因为您知道映射键总是从 1 到 N你也可以不用递归来解决这个问题：package mainimport "fmt"func main() {&nbsp; &nbsp; n := 10&nbsp; &nbsp; mm := make([]int, n+1)&nbsp; &nbsp; mm[0] = 1&nbsp; &nbsp; for i := 1; i <= n; i++ {&nbsp; &nbsp; &nbsp; &nbsp; for k := 1; k <= 3; k++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if i-k >= 0 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; mm[i] += mm[i-k]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; fmt.Println(mm)&nbsp; &nbsp; fmt.Println(mm[n])}

Answer 2

一个分而治之的Python解决方案：def staircase_count(nSteps):&nbsp; &nbsp; if nSteps < 0:&nbsp; &nbsp; &nbsp; &nbsp; return 0&nbsp; &nbsp; if nSteps == 0:&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; total = 0&nbsp; &nbsp; for step in [1, 2, 3]:&nbsp; &nbsp; &nbsp; &nbsp; total += staircase_count(nSteps - step)&nbsp; &nbsp; return totalassert staircase_count(1) == 1assert staircase_count(2) == 2assert staircase_count(3) == 4assert staircase_count(4) == 7

Answer 3

JavaScript 解决方案：（迭代）&nbsp; &nbsp;function countPossibleWaysIterative(n) {&nbsp; &nbsp; &nbsp; if (n < 0){&nbsp; &nbsp; &nbsp; &nbsp; return -1; // check for negative, also might want to check if n is an integer&nbsp; &nbsp; &nbsp; } if (n === 0) {&nbsp; &nbsp; &nbsp; &nbsp; return 0; // for case with 0 stairs&nbsp; &nbsp; &nbsp; } else if (n === 1) {&nbsp; &nbsp; &nbsp; &nbsp; return 1; // for case with 1 stairs&nbsp; &nbsp; &nbsp; } else if (n === 2) {&nbsp; &nbsp; &nbsp; &nbsp; return 2; // for case with 2 stairs&nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; var prev_prev = 1;&nbsp; &nbsp; &nbsp; &nbsp; var prev = 2;&nbsp; &nbsp; &nbsp; &nbsp; var res = 4; // for case with 3 stairs&nbsp; &nbsp; &nbsp; &nbsp; while (n > 3) { // all other cases&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var tmp = prev_prev + prev + res;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev_prev = prev;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev = res;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res = tmp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n--;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return res;&nbsp; &nbsp; }