地图和动态规划更新

Question

我得到的问题是一个孩子正在跑一个有 n 级台阶的楼梯，并且一次可以跳 1 级、2 级或 3 级。实施一种方法来计算孩子可以通过多少种可能的方式跑上楼梯。http://play.golang.org/p/bpjIkMm9jHpackage mainimport "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 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])

}

Answer 2

一个分而治之的Python解决方案：

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

Answer 3

JavaScript 解决方案：（迭代）

   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;

    }