一个人正在跑步一个有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]
