6

一个人跑上 n 级楼梯，一次可以走 1 级、2 级或 3 级。现在编写一个程序来计算孩子可以用多少种可能的方式跑楼梯。

给出的代码如下

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. 她为什么以及如何在这里使用功能图？这里的地图是数组对吗？

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

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

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

我将不胜感激。

多谢你们

4

5 回答 5

14

好的，这就是代码的作用。

 `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 步可获得的可能组合数量 + 用户走 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]
于 2013-07-22T03:24:34.587 回答
3

她为什么以及如何在这里使用功能图？

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

这里的地图是数组对吗？

正确，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)调用。但是，每次调用都会完成K项目的计算map（请注意map单向街道：一旦将非负值设置到单元格中，它将永远保持非负值，因此通过重新计算相同的值任何其他调用路径都将花费相同的O(1)时间。

于 2013-07-22T03:17:07.323 回答
0

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;
}
于 2014-11-29T01:05:00.770 回答
0

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) 快得多。

于 2013-07-22T03:22:17.960 回答
0 
/**
 * 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<Integer, Long> 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。对于被注释的行。有人可以评论为什么我的思维过程是错误的吗？

于 2016-03-04T05:28:52.497 回答