动态规划走楼梯
发布时间:2020-12-16 07:45:35 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 // // main.cpp // 动态规划走楼梯 // // Created by liujan on 11/18/14. // Copyright (c) 2014 liujan. All rights reserved. // /* 问题描述:一
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 // // main.cpp // 动态规划走楼梯 // // Created by liujan on 11/18/14. // Copyright (c) 2014 liujan. All rights reserved. // /* 问题描述:一个楼梯有20级,每次走1级或2级,从底走到 顶一共有多少种走法? 分析: 假设从底走到第n级的走法有f(n)种,走到第n级 有两个方法,一个是从第(n-1)级走1步,另一个是从第(n- 2)级走2步,前者有f(n-1)种方法,后者有f(n-2)种方法,所 以f(n)=f(n-1)+f(n-2),另外f(0)=1,f(1)=1 优化: 利用动态规划,将每层楼的走法保存下来,避免重复计算 */ #include <iostream> using namespace std; int result[100]; //保存到达每个楼梯的走法,为了避免重复计算 int move(int n){ if (result[n] > 0) //如果该楼梯此前求过,则直接返回先前的结果就可以了,避免重复求解 return result[n]; else{ int ans = 0; if (n == 0 || n == 1) ans = 1; else{ ans = move(n-1) + move(n-2); } result[n] = ans; //保存该楼层计算结果 return ans; } } int main(int argc,const char * argv[]) { // insert code here... memset(result,sizeof(int) * 100); cout << move(20) << endl; return 0; } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |