algorithm - map 和动态规划更新

Question

给我的问题是

一个 child 正跑上 n 级楼梯， 一次可以跳 1 步、2 步或 3 步。 实现一种方法来计算 child 可以通过多少种可能的方式跑上楼梯。

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 个 map[]。事实证明，动态递归在以下行结束:

else if mm[n] > -1

那我怎么用动态规划来解决这个问题呢？这与 Cracking the coding interview 中的解决方案完全相同......

Answer 1

你需要和0比较:

else if mm[n] > 0

当为不存在的键获取值时，map 返回 0。

您也可以使用数组/slice 代替映射，因为您知道映射键总是从 1 到 N

你也可以不用递归来解决这个问题:

package main

import "fmt"

func main() {
    n := 10
    mm := make([]int, n+1)
    mm[0] = 1
    for i := 1; i <= n; i++ {
        for k := 1; k <= 3; k++ {
            if i-k >= 0 {
                mm[i] += mm[i-k]
            }
        }
    }
    fmt.Println(mm)
    fmt.Println(mm[n])
}