Java 编程 : Dynamic Programming on stairs example

Question

一个人正在跑 n 步楼梯，一次可以走 1 步、2 步或 3 步。现在编写一个程序来计算 child 有多少种可能的跑楼梯方式。

给出的代码如下

public static 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]; }
 }

我懂 C 和 C++，不懂 JAVA。这是来自 Cracking the Coding 采访书。谁能解释一下

1. 她为什么以及如何在这里使用功能图？这里的map是数组吧？

2. 我没有看到任何行将输入保存到 map 数组，但它如何返回某些内容？

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

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

我将不胜感激。

谢谢大家

Answer 1

好的，下面是代码的作用。

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

如果剩余的步数不够，则不要计数。例如，如果还剩两步，但用户尝试走三步，则不算作可能的组合。

否则如果 (n==0) 返回1;

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

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

这里是动态规划部分。假设数组中的所有值的值为 -1。所以，如果这个数字大于-1，它已经被解决了，所以返回第 n 步的组合总数而不是解决它。

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

返回 map [n]； }

最后，这部分解决了代码。可能的组合数等于用户走1步可能得到的组合数+用户走2步可能得到的组合数+用户走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]