动态规划-------一个简单爬梯子问题 - CSDN博客
动态规划-------一个简单爬梯子问题
一个楼梯有20级，每次走1级或两级，请问从底走到顶一共有多少种走法？
分析：假设从底走到第n级的走法有f（n）种，走到第ｎ级有两个方法，一个是从（n-1)级走一步，另一个是从第（ｎ－２）级走两步，前者有f(n-1)种方法，后者有f(n-2)种方法，所以有f(n)=f(n-1)+f(n-2),还有f(0)=1,f(1)=1.递归编程实现程序１#include &stdio.h&int f(int n){&&& if(n==0 || n==1) return 1;&& else return f(n-1)+f(n-2);}int main(){&&&& printf("%d/n",f(20));&&& return 0;}现在来说说动态规划的基本思想动态规划的关键是发现子问题和怎么记录子问题，以上面的例子说明（１）对子问题可递归的求解，当n&1时，f(n)=f(n-1)+f(n-2);否则，f(1)=f(0)=1;(2)这些子问题是有重叠的，即求解某个问题时，某些子问题可能需要求解多次。例如求解f(5)时，f(2)就被求解了３次。在上面两个条件下，用动态规划的方式来求解会高效很多。就是把子问题记录下来，每个子问题只求解一次，从而提高了效率。程序２#include &stdio.h&int result[100];int f(int n){&　&　if(result[n]&=0) return result[n];&　if(n==0 || n==1) res=1;&　else res=f(n-1)+f(n-2);&　result[n]=&　}int main(){&　&　for(i=0;i&=20;i++)&&　　result[i]=-1;&　printf("%d/n",f(20));&　return 0;}程序３#include &stdio.h&int f[100];int main(){&　&　f[0]=1;　&f[1]=1;&　for(i=2;i&=20;i++)&&　　f[i]=f[i-1]+f[i-2];&　printf("%d",f[20]);&　return 0;}程序３是否让你想起了那个兔子繁殖的问题呢？
动态规划，采用分治的策略，把求最优解问题***为求若干子问题的最优解，记录子问题的解，化繁为简，很实用，也很高效。
本文已收录于以下专栏：
相关文章推荐
题目:一个人每次只能走一层楼梯或者两层楼梯，问走到第80层楼梯一共有多少种方法。
解题思想:设走第i层楼梯需要dp[i]中方法，走第i-1层楼梯需要dp[i-1]中方法。则走第
i+1层楼...
1.问题描述一个人爬楼梯，每次只能爬1个或两个台阶，假设有n个台阶，那么这个人有多少种不同的爬楼梯方法2.分析如果n==1，显然只有从0-&1一种方法f(1)=1；
如果n==2，那么有0-&1-&...
chuanbindeng 的 素数判断算法关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识，在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信对大家一定有帮助。    正如大家都知...
爬楼梯问题总结（持续更新）
因为最近做了几道爬楼梯问题，可自己还是不会做。
因为我刚开始用的自己的方法，没有学习通用方法（简单方法）
下面我还是来总结一下目前遇到的爬楼梯问题
如果有更好的爬楼梯问题，...
上楼梯问题
明明上楼梯有两种方法，每次上一级或者上两级台阶。如果有3级台阶，明明共有3种不同的上楼梯方法：
1 - 1 - 1 每次都上一级
1 - 2      第一次上一级，第二次上两级
题目来源于POJ，是一道非常基础的动态规划题目。但是却耗费了我非常多的时间，时间复杂度也从N的三次方，降到N的平方，最后优化到0(n)才最终得以通过。
题目如下：
要求其实非常简单，已知给你a1,a...
Google 曾询问应征者 ：有N阶楼梯 ，你每次只能爬1或2 阶 楼梯；能有多少种方法
对这个问题进行分析：  假设N阶楼梯的爬法有A（N）种；由于每次爬1或2阶 因此 A（N）= A（N-1）...
前一天睡前看了一道题，睡觉的时候想了想，一大早（误）起来写了一下交了然后就AC了。
嘿！太难得了！（……
感觉是思路很简单的一个动态规划，然后也没有做任何优化，连双关键字排序也只是写的选...
一直感觉 动态 规划和排列好难的
一个简单的题目。
 ?司，一个整日游手好闲、无所事事、混迹人生、软弱无能、放纵欲望、毫无进取……嗯，实在是太多了，就不一一列举了。总之，他就是完美的符合了...
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)