c/c++ LeetCode 爬楼梯

问题描述:

难度简单1164

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

**注意：**给定 n 是一个正整数;

解法一: 动态规划

状态转移方程 n == 1 dp[1] = 1;

n == 2 时 dp[2] = 2;

n == k 时 (k > 2) dp[k] = dp[k - 1] + dp[k - 2];

class Solution {public:    int climbStairs(int n) {        if (n == 1) return 1;        if (n == 2) return 2;        int* dp = new int[n + 1];        dp[1] = 1;        dp[2] = 2;                for (int i = 3; i <= n ; ++i) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }};

时空复杂度分析

时间复杂度: 从3 开始遍历到n 一遍所以为O(N);

空间复杂度: 用了一个长度为n + 1 数组保存所有的状态;为O (N);

解法二 : 迭代(最优解)

有些越简单的越实用,什么递归啊,动态规划呀,没啥用,递归时间复杂度太高

用三个变量交替赋值;

class Solution {public:    int climbStairs(int n) {        if (n == 1) return 1;        if (n == 2) return 2;        if (n == 3) return 3;        int left = 1;        int right = 2;        int sum = 0;        for (int i = 3 ;  i <= n; i++){            sum = left + right ;            left = right;            right = sum ;         }         return sum;    }};