Maple's Blog.

Leetcode-70

Leetcode
字数统计: 213阅读时长: 1 min
2019/02/27 Share

这是一个简单的DP，类似于斐波那契数列。
附上题目链接

实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<vector>
using namespace std;
vector <int>memo;
class Solution {
public:

    int climbStairs(int n) {

        vector<int> data(n + 1, -1);
        data[0] = 1;
        data[1] = 1;
        for(int i = 2 ; i <= n ; i ++)
            data[i] = data[i - 1] + data[i - 2];
        return data[n];
    }
};
int   main()
{
    int n;
    while(cin>>n)
    {
        cout<<Solution().climbStairs(n)<<endl;
    }
    return 0;
}

data[i] = data[i - 1] + data[i - 2];(考虑自底向上的做法)
要求n阶的台阶有多少种走法，可以先考虑走到台阶数为n-1和n-2的时候；然后n-1阶数的时候又可以考虑当台阶数为n-2和n-3；n-2阶数的时候又可以考虑当台阶数为n-3和n-4; 逐渐转换，然后求解…

原文作者：Maple

原文链接：http://yoursite.com/2019/02/27/Leetcode-70/

发表日期：February 27th 2019, 8:21:44 pm

更新日期：February 27th 2019, 8:30:18 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 51
2019
Leetcode 算法与数据结构 C++ 洛谷