栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

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

 `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步可获得的可能组合数量+用户迈出可获得的可能的组合数量三个步骤。

例如,假设有5个步骤

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

//The number of solutions from the fifth stepcountDp(5) = countDp(4)+countDp(3)+countDp(2);//Number of solutions from the fourth stepcountDP(4) = countDp(3)+countDp(2)+countDp(1);//Number of solutions from the third stepcountDp(3) = countDp(2)+countDp(1)+countDp(0);//Number of solutions from the second stepcountDp(2) = countDp(1)+countDp(0)+countDp(-1);//Number of solutions from the first stepcountDp(1) = countDp(0) + countDp(-1)+countDp(-2);//Finally, base casecountDp(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]


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/419786.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号