地图和动态编程更新

Question

The problem I am given is

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

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)
}

This just gives me 0 map[]. It turns out that the dynamic recursion ends at the following line:

else if mm[n] > -1

Then how would I use dynamic programming to solve this problem? This is exactly the same solution as in Cracking the coding interview....

Answer 1

You need to compare with 0:

else if mm[n] > 0

map returns 0 when getting values for non existing keys.

You can also use an array/slice instead of map as you know that the map keys are always from 1 to N

You can solve this without recursion as well:

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])
}