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

发布时间：2020-12-14 23:35:12 所属栏目：Java 来源：网络整理

导读：一个人正在跑步一个有n个台阶的楼梯,可以一次走1步,2步或3步.现在编写一个程序来计算孩子跑楼梯的可能方式. 给出的代码如下 public static int countDP(int n,int[] map) { if (n0) return 0; else if (n==0) return 1; else if (map[n]-1) return map[n]; e

一个人正在跑步一个有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的采访书.
任何人都可以解释一下

>为什么以及如何在这里使用功能图？这里的地图是阵列对吗？
>我没有看到任何行保存输入到地图数组,但它会如何返回一些东西？
>任何人都知道这个代码的C或C版本？很难理解这段代码.也许不是因为JAVA语法,而是动态编程的隐式结构.
>这个算法的时间复杂度是多少？它应该小于O(3 ^ n)？

我将不胜感激.

多谢你们

解决方法

好的,这是代码的作用.

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

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

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

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

否则if(map [n]> -1)
返回地图[n];

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

`map[n] = countDP(n-1,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]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!