动态规划--爬楼梯问题（入门）

动态规划算法要求将求解问题拆分为一系列相互交叠的子问题。

动态规划三要素：

• 最优子结构
• 边界
• 状态转移函数

问题描述：假设有n层台阶，你每次能爬1层或者2层，问你又多少种方法到达n层?

第一层：1种，记为f(1)=1（边界）

第二层：2种（走2步或走两个1步），记为f(2)=2

第三层：3种（在第一层走2步或在第二层走1步），记为f(3)=f(1)+f(2)

因此第n层就与第n-1和第n-2层有关。

输出：89

使用这种方式会出现重复计算的问题，因此，一般动态规划都会定义一个数组来存储前面所用到的值，修改后代码如下：

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!