首页 > 代码库 > careercup-递归和动态规划 9.1
careercup-递归和动态规划 9.1
9.1 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个方法，计算小孩有多少种上楼梯的方法。
解法：
我们可以采用自上而下的方式来解决这个问题。小孩上楼梯的最后一步，也就是抵达第n阶的那一步，可能走1阶、2阶或3阶。也就是说，最后一步可能是从第n-1阶往上走1阶、从n-2阶往上走2阶，或从第n-3阶往上走3阶。因此，抵达最后一阶的走法，其实就是抵达这最后三阶的方式的总和。
递归的方法实现：
int countWaysD(int n){ if(n<0) return 0; else if(n==0) return 1; else { return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3); }}
使用3个临时变量的方法：
int countWays(int n){ if(n<0) return 0; if(n==0) return 1; int first=0,second=0,third=1; int i=1; int ret; while(i<=n) { ret=first+second+third; first=second; second=third; third=ret; i++; } return ret;}
使用dp的方法，需要一个数组来记录前面已经求出的值。
int countWaysDP(int n,int dp[]){ if(n<0) return 0; if(n==0) return 1; if(dp[n]>0) return dp[n]; else dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp); return dp[n];}
C++实现代码：
#include<iostream>#include<cstring>#include<climits>using namespace std;const int MAX=1000;int countWaysD(int n){ if(n<0) return 0; else if(n==0) return 1; else { return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3); }}int countWays(int n){ if(n<0) return 0; if(n==0) return 1; int first=0,second=0,third=1; int i=1; int ret; while(i<=n) { ret=first+second+third; first=second; second=third; third=ret; i++; } return ret;}int countWaysDP(int n,int dp[]){ if(n<0) return 0; if(n==0) return 1; if(dp[n]>0) return dp[n]; else dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp); return dp[n];}int main(){ int dp[MAX]={0}; for(int i=1; i<10; i++) cout<<countWays(i)<<endl;}
careercup-递归和动态规划 9.1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。