Java编程：楼梯动态编程示例

一个人正在爬楼梯，有n个台阶，可以一次走1步，2步或3步。 现在编写一个程序来计算孩子跑楼梯的可能方式。

给出的代码如下

public static int countDP(int n, int[] map) { if (n-1) return map[n]; else { map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); return map[n]; } } 

我知道C和C ++，而不是JAVA。 这是来自Cracking the Coding的采访书。 任何人都可以解释一下

1. 为什么以及如何在这里使用function图？ 这里的地图是arrays吗？

2. 我没有看到任何行保存输入到地图数组，但它会如何返回一些东西？

3. 有人知道这段代码的C ++或C版本吗？ 很难理解这段代码。 也许不是因为JAVA语法，而是动态编程的隐式结构。

4. 这个算法的时间复杂度是多少？ 它应该小于O（3 ^ n）？

我将不胜感激。

多谢你们

Answer 1

好的，这是代码的作用。

  `if (n<0)` `return 0;` 

如果剩余的步骤不足，则不要计算。 例如，如果剩下两个步骤，但用户尝试采取三个步骤，则不会将其视为可能的组合。

else if (n==0) return 1;

如果剩余步数与用户尝试采用的可用步数相匹配，则可能是一种组合。 因此，返回1，因为这是一个可能的组合，应该添加到有效组合的总数中。

else if (map[n]>-1) return map[n];

这是动态编程部分。 假设数组中的所有值的值都为-1。 因此，如果数字大于-1，它已经被解决了，所以从步骤编号n返回组合的总数而不是解决它。

 `map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);` 

return map[n]; }

最后，这部分解决了代码。 可能组合的数量等于用户可以获得的可能组合的数量，如果他采取1步+用户可以获得的可能组合的数量，如果他采取2步+用户可以获得的可能组合的数量三个步骤。

举个例子，假设有5个步骤

一个简单的运行看起来像：

 //The number of solutions from the fifth step countDp(5) = countDp(4)+countDp(3)+countDp(2); //Number of solutions from the fourth step countDP(4) = countDp(3)+countDp(2)+countDp(1); //Number of solutions from the third step countDp(3) = countDp(2)+countDp(1)+countDp(0); //Number of solutions from the second step countDp(2) = countDp(1)+countDp(0)+countDp(-1); //Number of solutions from the first step countDp(1) = countDp(0) + countDp(-1)+countDp(-2); //Finally, base case countDp(0) = 1; countDp(-1)= 0; countDp(-2)= 0; countDp(1) = 1+0+0 = 1; countDp(2) = 1+1+0 = 2; //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1] countDp(3) = 2+1+1 = 4; //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2] countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1] countDp(5)= 2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2] 

Answer 2

为什么以及如何在这里使用function图？

这本书展示了一种称为memoization的动态编程技术。 它用于避免再次计算相同的数字：如果元素不是-1 ，那么它已经被再次计算，并且重新计算它将意味着浪费大量的CPU周期。 DP计算一次值，然后在每次需要值时返回它。

这里的地图是arrays吗？

正确， map是数组类型。

我没有看到任何行保存输入到地图数组，但它会如何返回一些东西？

这将是从底部开始的第三行的分配：

 map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

有人知道这段代码的C ++或C版本吗？ 很难理解这段代码。 也许不是因为JAVA语法，而是动态编程的隐式结构。

对，DP和memoization需要一些时间来习惯。 用纸和铅笔运行一次这个算法一小部分，比如说10个。这将告诉你答案的最佳子结构如何帮助这个算法如此快速地得出答案。

这个算法的时间复杂度是多少？ 它应该小于O（3 ^ n）？

绝对！ 每个项目只计算一次，每个项目按摊销O(1)进行计算，因此该代码的总体复杂度为O(N) 。 这可能是违反直觉的，因为您观察到计算countDP(K)的递归调用链如何进行O(K)递归调用。 但是，每次调用都会完成map K项的计算（请注意map是单行道的：一旦将非负值设置为单元格，它将永远保持非负数，因此重新计算通过任何其他调用路径的相同值将花费相同的O(1)时间。

Answer 3

1.）map是一个整数数组。 Java中的表示法是map [n]返回索引n处的整数值。

2.）返回是一个整数，因为map [n]返回索引n处的整数值。 值保存到数组的唯一时间是

 map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

这是一个递归调用，通过计算所有可能的1,2和3组合来查找步数之和。

3.）

 int countDP(int n, int map[]) { if (n<0) return 0; else if (n==0) return 1; else if (map[n]>-1) return map[n]; else { map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); return map[n]; } } 

4.）是的，复杂性将比O（3 ^ n）快得多。

Answer 4

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

Answer 5

 /** * Created by mona on 3/3/16. */ import java.util.Hashtable; public class StairCount { /* A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, or 3 steps at a time. count how many possible ways the child can run the stairs. */ static Hashtable ht=new Hashtable<>(); public static long stairs(int n){ if (!ht.containsKey(1)){ ht.put(1, (long) 1); } if (!ht.containsKey(2)){ ht.put(2, (long) 2); } if (!ht.containsKey(3)){ ht.put(3, (long) 4); } /* if (!ht.containsKey(n)){ ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3)); } */ if (!ht.containsKey(n)){ ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3)); } return ht.get(n); } public static void main(String[] args){ System.out.println(stairs(4)); } } 

// 4的答案是14，而5的答案是27.对于评论的行。 有人可以评论为什么我的思维过程错了吗？