Map and Dynamic Programming Updating

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....

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

A divide and conquer Python solution:

def staircase_count(nSteps):
    if nSteps < 0:
        return 0
    if nSteps == 0:
        return 1
    total = 0
    for step in [1, 2, 3]:
        total += staircase_count(nSteps - step)
    return total

assert staircase_count(1) == 1
assert staircase_count(2) == 2
assert staircase_count(3) == 4
assert staircase_count(4) == 7

JavaScript solution: ( iterative )

   function countPossibleWaysIterative(n) {
      if (n < 0){
        return -1; // check for negative, also might want to check if n is an integer
      } if (n === 0) {
        return 0; // for case with 0 stairs
      } else if (n === 1) {
        return 1; // for case with 1 stairs
      } else if (n === 2) {
        return 2; // for case with 2 stairs
      } else {
    
        var prev_prev = 1;
        var prev = 2;
        var res = 4; // for case with 3 stairs
    
        while (n > 3) { // all other cases
          var tmp = prev_prev + prev + res;
          prev_prev = prev;
          prev = res;
          res = tmp;
          n--;
        }
      }
      return res;
    }