[数据结构与算法]爬楼梯问题（动态规划）

题目

分析

• 算法思路：如先从第m级考虑，设走到m级方案共F(m)种，根据题意，走到第m级台阶的上一级只能是第m-1、m-2级和m-3级。即F（m)=F(m-1)+F(m-2)+F(m-3)，而F(1),F(2),F(3)是很容易得出的，从而可以求出F(4)。同理可以依次求出够多级数对应的方案数量。
• 最朴素的思路：定义一个数组，通过循环，得出F(m)的值。
• 优化算法一（空间换时间）：定义一个数组f[20]，根据题给用循环语句，算出范围内每个f[i]的值，输出所需级数对应的元素即可。
• 优化算法二（动态规划）：定义四个变量，边走边存边修改。如由a,b,c分别存储f1,f2,f3的值，可以得出由d存储的f4的值，再将b,c,d所存储的f2,f3,f4可以求出的f5的值存放在a中，同理依次循环至所求级数即可。

优化算法一（空间换时间）的代码：

#include<iostream>
using namespace std;
int main()
{
  int m, a[50];
  a[1] = 1; a[2] = 2; a[3] = 4;
  cin >> m;
  for (int i = 3; i < 50; i++)
  {
   a[i] = a[i-1] + a[i-2] + a[i-3];
  }
  cout << a[m];
}