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

Java Programming : Dynamic Programming on stairs example

提问by jmpyle771

A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, or 3 steps at a time. Now write a program to count how many possible ways the child can run the stairs.

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

The code given is like below

给出的代码如下

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

I know C and C++, not JAVA. This is from the Cracking the Coding interview book. Could anybody can explain

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

1. why and how she employs the function map here? map here is array right?

2. I do not see any line to save an input to the map array but how would it return something?

3. Anybody has an idea of C++ or C version of this code? It is hard to understand this code. Maybe not because of the JAVA grammar, but the implicit structure of dynamic programming.

4. What would be the time complexity of this algorithm? It should be smaller than O(3^n) ?

1. 她为什么以及如何在这里使用函数映射？这里的地图是数组吗？

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

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

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

I would greatly appreciate it.

我将不胜感激。

Thanks, guys

多谢你们

回答by jmpyle771

Okay, here is what the code does.

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

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

If there aren't enough steps remaining, then don't count it. For instance, if there are two steps remaining, but the user is trying to take three steps, then it does not count as a possible combination.

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

else if (n==0)return 1;

else if (n==0)return 1;

If the number of steps remaining matches the number of available steps the user is trying to take, it is a possible combination. So, return a 1 because this is a possible combination and should be added to the total number of valid combinations.

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

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

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

Here is the dynamic programming part. Assume that the all the values in the array had a value of -1. So, if the number is greater than -1, it has already been solved for, so return the total number of combinations from step number n instead of resolving it.

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

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

return map[n]; }

return map[n]; }

Finally, this part solves the code. The number of possible combinations is equal to the number of possible combinations the user can get if he takes 1 step + the number of possible combinations the user can get if he takes 2 steps + the number of possible combinations the user can get if he takes three steps.

最后，这部分解决了代码。可能的组合数等于用户走1步能得到的可能组合数+用户走2步能得到的可能组合数+用户走2步能得到的可能组合数三个步骤。

An example, suppose there are 5 steps

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

A simple run would look like:

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

//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]

回答by dasblinkenlight

why and how she employs the function map here?

她为什么以及如何在这里使用函数映射？

The book shows a dynamic programming technique called memoization. It is used to avoid calculating the same number again: if the element is not -1, then it has been computed again, and re-calculating it would mean wasting lots of CPU cycles. DP computes the value once, and then returns it every time the value is needed.

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

map here is array right?

这里的地图是数组吗？

Correct, mapis of an array type.

正确，map是数组类型。

I do not see any line to save an input to the map array but how would it return something?

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

That would be the assignment on the third line from the bottom:

这将是从底部算起的第三行的赋值：

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

Anybody has an idea of C++ or C version of this code? It is hard to understand this code. Maybe not because of the JAVA grammar, but the implicit structure of dynamic programming.

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

Right, DP and memoization take some time to get used to. Run through this algorithm once with paper and pencil for a small number, say, 10. This will show you how the optimal substructure of the answer helps this algorithm come up with the answer so fast.

对，DP和记忆需要一些时间来适应。用纸和铅笔运行一次这个算法，得到一个小数字，比如 10。这将向你展示答案的最佳子结构如何帮助这个算法如此快速地得出答案。

What would be the time complexity of this algorithm? It should be smaller than O(3^n) ?

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

Absolutely! Each item is computed exactly once, and each item takes amortized O(1)to compute, so the overall complexity of this code is O(N). This may be counterintuitive, as you observe how the chain of recursive invocations to compute countDP(K)takes an O(K)recursive invocations. However, each invocation finishes the computation of Kitems of the map(note how mapis a one-way street: once you set a non-negative value into a cell, it's going to stay non-negative forever, so re-computing the same value through any other invocation path would take the same O(1)time.

绝对地！每个项目只计算一次，每个项目都需要分期O(1)计算，所以这段代码的整体复杂度为O(N)。这可能违反直觉，因为您观察到计算countDP(K)的O(K)递归调用链如何进行递归调用。但是，每次调用完成的计算K中的项目map（注意如何map是单行道：一旦你设置一个非负值进入细胞，它会永远留非负，所以重新计算通过相同的值任何其他调用路径都需要相同的O(1)时间。

回答by newtonrd

1.) map is an integer array. The notation in Java is that map[n] returns the integer value at index n.

1.) map 是一个整数数组。Java 中的符号是 map[n] 返回索引 n 处的整数值。

2.) The return is an integer because map[n] returns the integer value at index n. The only time a value is saved to the array is at

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

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

This is a recursive call to find the sum of steps by counting all the possible 1 , 2, and 3 combinations.

这是一个递归调用，通过计算所有可能的 1 、 2 和 3 组合来找到步骤的总和。

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.) Yes the complexity would be much faster than O(3^n).

4.) 是的，复杂度会比 O(3^n) 快得多。

回答by spark

JavaScript solution: ( iterative )

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

回答by Mona Jalal

/**
 * 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));

    }
}

//the answer for 4 is 14 and for 5 is 27. For the line that is commented. Can someone comment why my thought process were wrong?

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