509. 斐波那契数

题目链接
文章讲解

class Solution {
public:int fib(int n) {// 1. 确定 DP 数组及下标的含义：//    dp[i] 表示第 i 个斐波那契数//    例如 dp[0] = 0, dp[1] = 1, dp[2] = 1, dp[3] = 2, dp[4] = 3, ...vector<int> dp;// 2. 确定递推公式：//    斐波那契数列的递推公式为：//    dp[i] = dp[i - 1] + dp[i - 2]，其中 i >= 2//    也就是当前数等于前两个数的和。// 3. DP 数组如何初始化：//    - dp[0] = 0，dp[1] = 1，分别表示斐波那契数列的前两个数。//    - 如果 n 是 0 或 1，直接返回 n，本身就是结果。if (n == 0 || n == 1) return n;// 初始化前两个数dp.push_back(0);  // dp[0] = 0dp.push_back(1);  // dp[1] = 1// 4. 确定遍历顺序：//    从 i = 2 开始，遍历直到 n，使用递推公式计算 dp 数组的值。//    由于 dp[i] 依赖于 dp[i-1] 和 dp[i-2]，因此我们从小到大依次计算。for (int i = 2; i <= n; i++) {dp.push_back(dp[i - 1] + dp[i - 2]);}// 5. 举例推导 DP 数组：//    假设 n = 5，执行过程如下：//    dp[0] = 0, dp[1] = 1//    i = 2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1//    i = 3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2//    i = 4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3//    i = 5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5//    最终 dp 数组为 [0, 1, 1, 2, 3, 5]，返回 dp[5] = 5return dp.back();  // 返回斐波那契数列的第 n 个数}
};

70. 爬楼梯

题目链接
文章讲解

class Solution {
public:int climbStairs(int n) {vector<int> dp;  // 1. 确定 DP 数组及下标的含义：dp[i] 表示到达第 i 阶楼梯的不同方式数dp.push_back(0);  // dp[0] = 0, 不考虑 0 阶楼梯的情况dp.push_back(1);  // dp[1] = 1, 只有 1 阶时，只有一种方式（一步到达）dp.push_back(2);  // dp[2] = 2, 2 阶楼梯时，可以一步一步走或直接两步走（两种方式）// 2. 确定递推公式：//    对于每一阶楼梯，当前楼梯的到达方式数等于前一阶楼梯和前两阶楼梯方式数之和//    dp[i] = dp[i-1] + dp[i-2]// 3. DP 数组如何初始化：//    dp[0], dp[1], dp[2] 已经在上面初始化了，表示 0 阶、1 阶、2 阶的方式数。//    如果 n <= 3，则直接返回 n，因为对于小于等于 3 的楼梯，直接返回即可。if (n <= 3) return n;// 4. 确定遍历顺序：//    从 i = 3 开始，使用递推公式填充 dp 数组for (int i = 3; i <= n; i++) {dp.push_back(dp[i-1] + dp[i-2]);  // 当前阶梯的方式数等于前一阶和前两阶方式数之和}// 5. 举例推导 DP 数组：//    假设 n = 4：//    dp[0] = 0, dp[1] = 1, dp[2] = 2//    i = 3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3//    i = 4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5//    dp 数组最终为 [0, 1, 2, 3, 5]，返回 dp[4] = 5，即到达第 4 阶楼梯的方式数是 5return dp.back();  // 返回 dp[n]，即到达第 n 阶楼梯的方式数}
};

746. 使用最小花费爬楼梯

题目链接
文章讲解

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {// 1. 确定 DP 数组及下标的含义：//    dp[i] 表示到达第 i 阶楼梯的最小花费//    dp[0] 和 dp[1] 分别表示到达第 0 阶和第 1 阶的花费。vector<int> dp(cost.size() + 1);  // dp 数组大小为 cost 数组大小 + 1// 2. 确定递推公式：//    对于每个阶梯 i (i >= 2)，到达这个阶梯的最小花费是：//    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])//    也就是说，从第 i - 1 阶跳到第 i 阶，或者从第 i - 2 阶跳到第 i 阶，取其中较小的花费。// 3. DP 数组如何初始化：//    dp[0] 和 dp[1] 表示到达第 0 和第 1 阶楼梯的花费，初始化为 0。//    因为可以从第 0 阶或者第 1 阶开始，所以它们的花费为 0。dp[0] = 0;dp[1] = 0;// 4. 确定遍历顺序：//    从 i = 2 开始遍历，使用递推公式填充 dp 数组。for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}// 5. 举例推导 DP 数组：//    假设 cost = [10, 15, 20]：//    dp[0] = 0, dp[1] = 0//    i = 2: dp[2] = min(dp[1] + cost[1], dp[0] + cost[0]) = min(0 + 15, 0 + 10) = 10//    i = 3: dp[3] = min(dp[2] + cost[2], dp[1] + cost[1]) = min(10 + 20, 0 + 15) = 15//    最终 dp 数组为 [0, 0, 10, 15]，返回 dp[3] = 15，即最小花费是 15。// 6. 返回结果：return dp.back();  // 返回 dp 数组的最后一个元素，即到达顶楼的最小花费}
};