leetcode70：爬楼梯

题目链接

leetcode

题目描述

假设你正在爬楼梯。需要n 阶你才能到达楼顶。
每次你可以爬1或2个台阶。
有多少种不同的方法可以爬到楼顶？

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    状态表示：
        f[i] 表示爬一个 i 级楼梯有多少种走法
    状态计算：
        f[i] = f[i - 1] + f[i - 2], i >= 2
    
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    int climbStairs(int n) {
        if (n == 0) return 1;
        if (n <= 2) return n;

        int f[n + 1];
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i ++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f[n];
    }
};

/*
    优化空间：三个变量保存元素，来回替换

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    int climbStairs(int n) {
        if (n == 0) return 1;
        if (n <= 2) return n;

        int first = 1, second = 2, count = 0;
        for (int i = 3; i <= n; i ++) {
            count = first + second;
            first = second;
            second = count;
        }

        return count;
    }
};

int main() {
    Solution solution;
    int n;
    vector<int> test_cases = { 2, 3 };

    for (auto& num : test_cases) {
        cout << "Input: " << num << endl;
        cout << "Output: " << solution.climbStairs(num) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   动态规划：
       使用一个数组 dp，其中 dp[i] 表示爬到第 i 级楼梯的方法数。
       初始化 dp[1] = 1 和 dp[2] = 2。
       对于 i >= 3，dp[i] = dp[i-1] + dp[i-2]，
	   因为爬到第 i 级楼梯的方法数等于爬到第 i-1 级和第 i-2 级的方法数之和。
   边界条件：
       如果 n <= 2，直接返回 n，因为爬到第 1 级有 1 种方法，爬到第 2 级有 2 种方法。
       如果 n == 0，返回 0，因为没有楼梯可爬。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)，其中 n 是楼梯的级数。
   空间复杂度：O(n)
       使用了一个大小为 n+1 的数组 dp，空间复杂度为 O(n)。
*/
// climbStairs 计算爬到第 n 级楼梯的方法数
func climbStairs(n int) int {
    if n <= 2 {
		return n
	}
    
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2

	for i := 3; i <= n; i ++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

/*
    优化空间：三个变量保存元素，来回替换

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
func climbStairs_1(n int) int {
    if n <= 2 {
		return n
	}

	first, second, count := 1, 2, 0
	for i := 3; i <= n; i++ {
		count = first + second
        first = second
        second = count
	}

	return count
}

func main() {
	// 测试用例
	testCases := []struct {
		n        int
		expected int
	}{
		{
			n:        2,
			expected: 2,
		},
		{
			n:        3,
			expected: 3,
		},
	}

	for i, tc := range testCases {
		result := climbStairs(tc.n)
		fmt.Printf("Test Case %d, Input: n = %d\n", i+1, tc.n)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}