题解

题目难度：中等难度

难点：

1.怎么找到不同楼梯阶数之间的转化关系。

2.可能的方式巨多，超出整型范围，需要用字符串进行存储

知识点：动态规划，大数求和

思路：

一：怎么找到不同楼梯阶数的转化关系。

1.当只有1层时只有一种走法，即f1=1。

2.当只有2层时也只有一种做法，即f2=1。

3.当只有3层时，有两种走法（一次3阶，3次每一1阶），即f3=2。

4.当只有4层时：

第一类：在走完1层之后，再走一个3阶，即f1。

第二类：在走完3层之后，再走一个1阶，即f3。

所以只有4层时一共的走法为f4=f1+f3。

5.当只有5层时：

第一类：在走完2层之后，再走一个3阶，即f2。

第二类：在走完4层之后，再走一个1阶，即f4。

所以只有5层时一共的走法为f5=f2+f4。

n . 当只有n层时：

第一类：在走完n-3层之后，再走一个3阶，即fn-3。

第二类：在走完n-1层之后，再走一个1阶，即fn-1。

所以只有n层时一共的走法为fn=fn-3+fn-1。

若n较小时（不超过整数的取值范围）可以利用下面转化方式：

temp1=f1;
temp2=f2;
temp3=f3;
int temp;
for(int i=4;i<=n;i++){
    temp=temp3+temp1;
    temp1=temp2;
    temp2=temp3;
    temp3=temp;
}
cout<<temp;

二：考虑存储越界，使用字符串数组进行存储

根据fn=fn-1+fn-3；

将fn-1放入vector a中，将fn-3放入vector b中：（这里的数据随便假设的，只是为了说明计算思想）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 510;
vector<int> dp[N];
int n;
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++)
    {
      if (i < a.size()) t += a[i];
      if (i < b.size()) t += b[i];
      c.push_back(t % 10);
      t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}
int main()
{
    cin >> n;
    dp[0] = vector<int> (1, 1);
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];
        if (i >= 3) dp[i] = add(dp[i], dp[i - 3]);
    }
    for (int i = dp[n].size() - 1; i >= 0; i --) cout << dp[n][i];
    return 0;
}

题解

题目难度：中等难度

难点：

1.怎么找到不同楼梯阶数之间的转化关系。

2.可能的方式巨多，超出整型范围，需要用字符串进行存储

知识点：动态规划，大数求和

思路：

一：怎么找到不同楼梯阶数的转化关系。

1.当只有1层时只有一种走法，即f1=1。

2.当只有2层时也只有一种做法，即f2=1。

3.当只有3层时，有两种走法（一次3阶，3次每一1阶），即f3=2。

4.当只有4层时：

第一类：在走完1层之后，再走一个3阶，即f1。

第二类：在走完3层之后，再走一个1阶，即f3。

所以只有4层时一共的走法为f4=f1+f3。

5.当只有5层时：

第一类：在走完2层之后，再走一个3阶，即f2。

第二类：在走完4层之后，再走一个1阶，即f4。

所以只有5层时一共的走法为f5=f2+f4。

n . 当只有n层时：

第一类：在走完n-3层之后，再走一个3阶，即fn-3。

第二类：在走完n-1层之后，再走一个1阶，即fn-1。

所以只有n层时一共的走法为fn=fn-3+fn-1。

若n较小时（不超过整数的取值范围）可以利用下面转化方式：

temp1=f1;
temp2=f2;
temp3=f3;
int temp;
for(int i=4;i<=n;i++){
    temp=temp3+temp1;
    temp1=temp2;
    temp2=temp3;
    temp3=temp;
}
cout<<temp;

二：考虑存储越界，使用字符串数组进行存储

根据fn=fn-1+fn-3；

将fn-1放入vector a中，将fn-3放入vector b中：（这里的数据随便假设的，只是为了说明计算思想）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 510;
vector<int> dp[N];
int n;
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || i < b.size(); i ++)
    {
      if (i < a.size()) t += a[i];
      if (i < b.size()) t += b[i];
      c.push_back(t % 10);
      t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}
int main()
{
    cin >> n;
    dp[0] = vector<int> (1, 1);
    for (int i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];
        if (i >= 3) dp[i] = add(dp[i], dp[i - 3]);
    }
    for (int i = dp[n].size() - 1; i >= 0; i --) cout << dp[n][i];
    return 0;
}