地图和动态规划更新

huangapple
go评论186阅读模式
英文:

Map and Dynamic Programming Updating

问题

我给出的问题是：

一个孩子正在一个有n个台阶的楼梯上跑步，他可以一次跳1个台阶、2个台阶或者3个台阶。实现一个方法来计算孩子上楼梯的可能方式有多少种。

这段代码的链接是：

  1. package main
  3. import "fmt"
  5. func CountWaysDP(n int, mm map[int]int) int {
  6.   if n < 0 {
  7.     return 0
  8.   } else if n == 0 {
  9.     return 1
  10.   } else if mm[n] > -1 {
  11.     return mm[n]
  12.   } else {
  13.     mm[n] = CountWaysDP(n-1, mm) +
  14.       CountWaysDP(n-2, mm) +
  15.       CountWaysDP(n-3, mm)
  16.     return mm[n]
  17.   }
  18. }
  20. func main() {
  21.   mm := make(map[int]int)
  22.   fmt.Println(CountWaysDP(10, mm), mm)
  23. }

这段代码只给出了0 map[]。事实证明，动态递归在以下一行结束：

  1. else if mm[n] > -1

那么我该如何使用动态规划来解决这个问题呢？这与《程序员面试金典》中的解决方案完全相同...

英文:

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

  1. package main
  3. import &quot;fmt&quot;
  5. func CountWaysDP(n int, mm map[int]int) int {
  6.   if n &lt; 0 {
  7.     return 0
  8.   } else if n == 0 {
  9.     return 1
  10.   } else if mm[n] &gt; -1 {
  11.     return mm[n]
  12.   } else {
  13.     mm[n] = CountWaysDP(n-1, mm) +
  14.       CountWaysDP(n-2, mm) +
  15.       CountWaysDP(n-3, mm)
  16.     return mm[n]
  17.   }
  18. }
  20. func main() {
  21.   mm := make(map[int]int)
  22.   fmt.Println(CountWaysDP(10, mm), mm)
  23. }

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

  1. else if mm[n] &gt; -1

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

答案1

得分: 2

你需要与0进行比较：

  1. else if mm[n] > 0

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

你也可以使用数组/切片代替map，因为你知道map的键总是从1到N。

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

  1. package main
  3. import "fmt"
  5. func main() {
  6.     n := 10
  7.     mm := make([]int, n+1)
  8.     mm[0] = 1
  9.     for i := 1; i <= n; i++ {
  10.         for k := 1; k <= 3; k++ {
  11.             if i-k >= 0 {
  12.                 mm[i] += mm[i-k]
  13.             }
  14.         }
  15.     }
  16.     fmt.Println(mm)
  17.     fmt.Println(mm[n])
  18. }
英文:

You need to compare with 0:

  1. else if mm[n] &gt; 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:

  1. package main
  3. import &quot;fmt&quot;
  5. func main() {
  6.     n := 10
  7.     mm := make([]int, n+1)
  8.     mm[0] = 1
  9.     for i := 1; i &lt;= n; i++ {
  10.         for k := 1; k &lt;= 3; k++ {
  11.             if i-k &gt;= 0 {
  12.                 mm[i] += mm[i-k]
  13.             }
  14.         }
  15.     }
  16.     fmt.Println(mm)
  17.     fmt.Println(mm[n])
  18. }

答案2

得分: 0

一个分治法的Python解决方案：

  1. def staircase_count(nSteps):
  2.     if nSteps < 0:
  3.         return 0
  4.     if nSteps == 0:
  5.         return 1
  6.     total = 0
  7.     for step in [1, 2, 3]:
  8.         total += staircase_count(nSteps - step)
  9.     return total
  11. assert staircase_count(1) == 1
  12. assert staircase_count(2) == 2
  13. assert staircase_count(3) == 4
  14. assert staircase_count(4) == 7
英文:

A divide and conquer Python solution:

  1. def staircase_count(nSteps):
  2.     if nSteps &lt; 0:
  3.         return 0
  4.     if nSteps == 0:
  5.         return 1
  6.     total = 0
  7.     for step in [1, 2, 3]:
  8.         total += staircase_count(nSteps - step)
  9.     return total
  11. assert staircase_count(1) == 1
  12. assert staircase_count(2) == 2
  13. assert staircase_count(3) == 4
  14. assert staircase_count(4) == 7

答案3

得分: -1

JavaScript解决方案：（迭代）

  1. function countPossibleWaysIterative(n) {
  2.   if (n < 0){
  3.     return -1; // 检查负数，也可以检查n是否为整数
  4.   } if (n === 0) {
  5.     return 0; // 对于0个台阶的情况
  6.   } else if (n === 1) {
  7.     return 1; // 对于1个台阶的情况
  8.   } else if (n === 2) {
  9.     return 2; // 对于2个台阶的情况
  10.   } else {
  12.     var prev_prev = 1;
  13.     var prev = 2;
  14.     var res = 4; // 对于3个台阶的情况
  16.     while (n > 3) { // 其他情况
  17.       var tmp = prev_prev + prev + res;
  18.       prev_prev = prev;
  19.       prev = res;
  20.       res = tmp;
  21.       n--;
  22.     }
  23.   }
  24.   return res;
  25. }
英文:

JavaScript solution: ( iterative )

  1.    function countPossibleWaysIterative(n) {
  2.       if (n &lt; 0){
  3.         return -1; // check for negative, also might want to check if n is an integer
  4.       } if (n === 0) {
  5.         return 0; // for case with 0 stairs
  6.       } else if (n === 1) {
  7.         return 1; // for case with 1 stairs
  8.       } else if (n === 2) {
  9.         return 2; // for case with 2 stairs
  10.       } else {
  11.     
  12.         var prev_prev = 1;
  13.         var prev = 2;
  14.         var res = 4; // for case with 3 stairs
  15.     
  16.         while (n &gt; 3) { // all other cases
  17.           var tmp = prev_prev + prev + res;
  18.           prev_prev = prev;
  19.           prev = res;
  20.           res = tmp;
  21.           n--;
  22.         }
  23.       }
  24.       return res;
  25.     }

huangapple
  • 本文由 发表于 2014年3月31日 17:41:41
  • 转载请务必保留本文链接：https://go.coder-hub.com/22758328.html
  • algorithm
  • dictionary
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定