指南：

https://www.hello-algo.com/chapter_dynamic_programming/intro_to_dynamic_programming/

Rust运行环境：

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021
1. 爬楼梯link
2. 爬楼梯扩展link

给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶，请问有多少种方案可以爬到楼顶？

def dp(i:int)->int:
    if i == 1 or i == 2:
        return i
    return dp(i - 1) + dp(i - 2)
n = int(input())
print(dp(n))

给定一个共有 $n$ 阶的楼梯，你每步可以上 $1$ 阶或者 $2$ 阶 $\color{pink}{或者3阶}$，请问有多少种方案可以爬到楼顶？

输入：
4
输出：
7

直观解法：
题意求方案数量，我们可以考虑通过回溯来穷举所有可能性。
从地面出发，走1-2阶，到达楼顶时方案数加一，越过则剪枝break

from typing import List

def backtrack(choices: List[int], state: int, n: int, res: List[int]) -> int:
    """回溯"""
    # 当爬到第 n 阶时，方案数量加 1
    if state == n:
        res[0] += 1
    # 遍历所有选择
    for choice in choices:
        # 剪枝：不允许越过第 n 阶
        if state + choice > n:
            continue
        # 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res)
        # 回退

def climbing_stairs_backtrack(n: int) -> int:
    """爬楼梯：回溯"""
    choices = [1, 2, 3]  # 可选择向上爬 1 阶或 2 阶, 3阶也可以
    state = 0  # 从第 0 阶开始爬
    res = [0]  # 使用 res[0] 记录方案数量
    backtrack(choices, state, n, res)
    return res[0]

n = int(input())
print(climbing_stairs_backtrack(n))

Rust:

use std::io;

fn backtrack(choices: &[i32], state: i32, n: i32, res: &mut [i32]) {
    // 当爬到第 n 阶时，方案数量加 1
    if state == n {
        res[0] += 1;
    }
    // 遍历所有选择
    for &choice in choices {
        // 剪枝：不允许越过第 n 阶
        if state + choice > n {
            continue;
        }
        // 尝试：做出选择，更新状态
        backtrack(choices, state + choice, n, res);
        // 回退
    }
}

fn climbing_stairs_backtrack(n: usize) -> i32 {
    let choices = vec![1, 2]; // 可选择向上爬 1 阶或 2 阶
    let state = 0; // 从第 0 阶开始爬
    let mut res = vec![0]; // 使用 res[0] 记录方案数量
    backtrack(&choices, state, n as i32, &mut res);
    res[0]
}

fn main() {
    // 读取用户输入
    let mut input = String::from("4"); //let mut input = String::new();
    io::stdin().read_line(&mut input).expect("Failed to read line");
    let n: usize = input.trim().parse().expect("Please enter a number");

    // 调用爬楼梯函数并打印结果
    let result = climbing_stairs_backtrack(n);
    println!("{}", result);
}