logo标签列表

Java编程：楼梯问题的动态规划示例

javaalgorithmrecursiontime-complexitydynamic-programming
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。这段话来自《破解编程面试》一书。 有人能解释一下：

  1. 为什么要在这里使用函数map？ map在这里是数组吗？

  2. 我没有看到任何一行将输入保存到map数组中，但它如何返回结果？

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

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

非常感谢。
谢谢大家
相关链接：https://dev59.com/f2ct5IYBdhLWcg3wNq6v - arshajii
我会尽力回答这个（晦涩难懂的）问题：
  1. map是一个int数组。
  2. 它必须在外部定义，即不在此示例中，并且必须包含n+1个元素。
  3. 不，如果你想得到答案，你必须将C和C++添加到标签中。
  4. ...
 - pstanton
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]; }

最后，这部分解决了代码。可能组合的数量等于用户在走一步时可能获得的组合数 + 用户在走两步时可能获得的组合数 + 用户在走三步时可能获得的组合数。

例如，假设有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]
3

为什么和如何在这里使用函数map?

这本书介绍了一种动态规划技术，称为记忆化。它用于避免再次计算相同的数字：如果元素不是-1，则已经重新计算过它，重新计算将意味着浪费大量的CPU周期。DP只计算值一次，然后每次需要该值时返回它。

这里的map是数组对吗？

正确，map是一个数组类型。

我没有看到任何将输入保存到映射数组中的行，但它会返回什么？

那将是从底部第三行的赋值：

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

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

没错，动态规划和记忆化需要一些时间来适应。使用纸和笔在小数字（例如10）上运行一次此算法。这将向您展示最优子结构如何帮助此算法快速得出答案。

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

当然可以！每个项目只计算一次，每个项目的摊销成本为O(1)，因此此代码的总复杂度为O(N)。这可能与直觉相反，因为您观察到计算countDP(K)的递归调用链需要进行O(K)个递归调用。但是，每次调用都会完成map中K个项目的计算（请注意，map是单向的：一旦您将非负值设置到单元格中，它将永远保持非负，因此通过任何其他调用路径重新计算相同值将花费相同的O(1)时间）。
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。关于被注释的那一行，请问有人能解释一下为什么我的思路是错误的吗？

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接