门户型网站_旅游网站建设论文_怎么百度推广_山东济南seo整站优化费用

目录

一、1137. 第 N 个泰波那契数 - 力扣（LeetCode）

方法一：算法代码（使用一维数组）

代码思路分析

边界条件处理：

动态规划数组初始化：

状态转移：

返回结果：

方法二：算法代码（滚动数组优化）

代码思路分析

边界条件处理：

滚动数组优化：

状态转移：

返回结果：

代码优化点

空间复杂度：

时间复杂度：

边界条件优化：

代码逻辑验证

代码总结

优点：

适用场景：

二、 面试题 08.01. 三步问题 - 力扣（LeetCode）

算法代码： 

代码思路分析

问题定义：

动态规划定义：

边界条件：

取模运算：

填表过程：

返回结果：

代码优化思路

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

三、 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

解法一：算法代码

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

解法二：算法代码

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

 四、91. 解码方法 - 力扣（LeetCode）

方法一：算法代码（直接初始化）

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

问题：

1. 动态规划定义

2. 为什么 dp 表大小为 n

3. 代码的具体逻辑

4. 为什么不需要 n + 1 的大小

5. 与 n + 1 定义的对比

6. 总结

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

方法二：算法代码（添加辅助位置初始化）

代码思路分析

问题定义：

动态规划定义：

边界条件：

填表过程：

返回结果：

代码优化思路

空间优化：

滚动数组优化：

优化后的代码

优化后的代码分析

空间复杂度：

时间复杂度：

边界条件处理：

总结

原始代码：

优化后的代码：

---

一、1137. 第 N 个泰波那契数 - 力扣（LeetCode）

方法一：算法代码（使用一维数组）

class Solution {
public:int tribonacci(int n) {if (n == 0 || n == 1)return n;if(n==2)return 1;vector<int> dp(n + 1);           // dp[i] 表⽰：第 i 个泰波那契数的值。dp[0] = 0, dp[1] = 1, dp[2] = 1; // 初始化// 从左往右填表for (int i = 3; i <= n; i++)dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];// 返回结果return dp[n];}
};

这段代码实现了计算第 n 个泰波那契数（Tribonacci Number）的功能。泰波那契数列的定义如下：

• T(0) = 0

• T(1) = 1

• T(2) = 1

• T(n) = T(n-1) + T(n-2) + T(n-3) （对于 n >= 3）

代码思路分析

1. 边界条件处理：

   • 当 n 为 0 或 1 时，直接返回 n，因为 T(0) = 0，T(1) = 1。

   • 当 n 为 2 时，T(2) = 1。

2. 动态规划数组初始化：

   • 创建一个大小为 n + 1 的数组 dp，用于存储每个位置的泰波那契数。

   • 初始化 dp[0] = 0, dp[1] = 1, dp[2] = 1，这是泰波那契数列的前三个值。

3. 状态转移：

   • 从 i = 3 开始，逐个计算 dp[i]，直到 i = n。

   • 每个 dp[i] 的值由前三个数的和决定，即 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

4. 返回结果：

   • 最终返回 dp[n]，即第 n 个泰波那契数。

方法二：算法代码（滚动数组优化）

// 滚动数组优化
class Solution {
public:int tribonacci(int n) {if (n == 0)return 0;if (n == 1 || n == 2)return 1;int a = 0, b = 1, c = 1, d = 0;for (int i = 3; i <= n; i++) {d = a + b + c;a = b;b = c;c = d;}return d;}
};

这段代码是对泰波那契数列计算的优化版本，使用了滚动数组的思想来减少空间复杂度。以下是代码的思路分析：

---

代码思路分析

1. 边界条件处理：

   • 当 n == 0 时，直接返回 0，因为 T(0) = 0。

   • 当 n == 1 或 n == 2 时，直接返回 1，因为 T(1) = T(2) = 1。

2. 滚动数组优化：

   • 使用四个变量 a, b, c, d 来存储泰波那契数列的中间结果：

     • a 表示 T(i-3)

     • b 表示 T(i-2)

     • c 表示 T(i-1)

     • d 表示 T(i)

   • 每次计算 d = a + b + c，然后更新 a, b, c 的值，为下一次计算做准备。

3. 状态转移：

   • 从 i = 3 开始，循环到 i = n，每次计算当前值 d，并更新 a, b, c 的值：

     • d = a + b + c：计算当前泰波那契数。

     • a = b：将 b 的值赋给 a，表示 T(i-3) 更新为 T(i-2)。

     • b = c：将 c 的值赋给 b，表示 T(i-2) 更新为 T(i-1)。

     • c = d：将 d 的值赋给 c，表示 T(i-1) 更新为 T(i)。

4. 返回结果：

   • 最终返回 d，即第 n 个泰波那契数。

---

代码优化点

1. 空间复杂度：

   • 原始动态规划方法需要 O(n) 的空间来存储整个 dp 数组。

   • 滚动数组优化后，只需要 O(1) 的额外空间，仅用四个变量即可完成计算。

2. 时间复杂度：

   • 时间复杂度仍然是 O(n)，因为需要遍历从 3 到 n 的所有数。

3. 边界条件优化：

   • 当 n 为 0、1 或 2 时，直接返回结果，避免了不必要的计算。

---

代码逻辑验证

以 n = 4 为例，验证代码的正确性：

1. 初始化：

   • a = 0 (T(0))

   • b = 1 (T(1))

   • c = 1 (T(2))

   • d = 0 (未计算)

2. 循环过程：

   • i = 3：

     • d = a + b + c = 0 + 1 + 1 = 2 (T(3))

     • 更新：a = 1, b = 1, c = 2

   • i = 4：

     • d = a + b + c = 1 + 1 + 2 = 4 (T(4))

     • 更新：a = 1, b = 2, c = 4

3. 返回结果：

   • d = 4，即 T(4) = 4。

---

代码总结

• 优点：

  • 空间复杂度优化到 O(1)，适合处理较大的 n。

  • 代码简洁，逻辑清晰。

• 适用场景：

  • 需要计算泰波那契数列的场景，尤其是对空间复杂度有要求的场景。

二、 面试题 08.01. 三步问题 - 力扣（LeetCode）

算法代码： 

class Solution {
public:const int MOD = 1e9 + 7; // 定义模数int waysToStep(int n) {// 处理边界情况if (n == 1 || n == 2)return n;if (n == 3)return 4;// 创建 dp 表vector<int> dp(n + 1);// 初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;// 填表for (int i = 4; i <= n; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}// 返回结果return dp[n];}
};

        这段代码解决的问题是：计算爬楼梯的不同方式数，但每次可以爬 1 步、2 步或 3 步。由于结果可能非常大，需要对结果取模 1e9 + 7。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

   • 假设有 n 阶楼梯，每次可以爬 1 步、2 步或 3 步。

   • 求爬到第 n 阶楼梯的不同方式数。

2. 动态规划定义：

   • 定义 dp[i] 表示爬到第 i 阶楼梯的不同方式数。

   • 状态转移方程：

     • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

     • 因为最后一步可以是爬 1 步、2 步或 3 步。

3. 边界条件：

   • dp[1] = 1：只有 1 阶楼梯，只有一种方式。

   • dp[2] = 2：有两种方式（1+1 或 2）。

   • dp[3] = 4：有四种方式（1+1+1, 1+2, 2+1, 3）。

4. 取模运算：

   • 由于结果可能非常大，每次计算 dp[i] 时需要对 1e9 + 7 取模，防止溢出。

5. 填表过程：

   • 从 i = 4 开始，逐个计算 dp[i]，直到 i = n。

   • 每次计算 dp[i] 时，累加 dp[i-1], dp[i-2], dp[i-3]，并对结果取模。

6. 返回结果：

   • 最终返回 dp[n]，即爬到第 n 阶楼梯的方式数。

---

代码优化思路

1. 空间优化：

   • 当前代码使用了一个大小为 n + 1 的数组 dp，空间复杂度为 O(n)。

   • 由于每次计算 dp[i] 只需要前三个值，可以用滚动数组优化，将空间复杂度降低到 O(1)。

2. 滚动数组优化：

   • 使用三个变量 a, b, c 分别表示 dp[i-3], dp[i-2], dp[i-1]。

   • 每次计算当前值 d = (a + b + c) % MOD，然后更新 a = b, b = c, c = d。

---

优化后的代码

class Solution {
public:const int MOD = 1e9 + 7; // 定义模数int waysToStep(int n) {// 处理边界情况if (n == 1 || n == 2)return n;if (n == 3)return 4;// 使用滚动数组优化int a = 1, b = 2, c = 4; // 分别表示 dp[i-3], dp[i-2], dp[i-1]int d = 0; // 表示 dp[i]// 填表for (int i = 4; i <= n; i++) {d = ((a + b) % MOD + c) % MOD; // 计算 dp[i]a = b; // 更新 ab = c; // 更新 bc = d; // 更新 c}// 返回结果return d;}
};

---

优化后的代码分析

1. 空间复杂度：

   • 从 O(n) 降低到 O(1)，只使用了常数个变量。

2. 时间复杂度：

   • 仍然是 O(n)，因为需要遍历从 4 到 n 的所有数。

3. 边界条件处理：

   • 当 n 为 1、2 或 3 时，直接返回结果，避免了不必要的计算。

---

总结

• 原始代码：

  • 使用动态规划数组存储中间结果，适合初学者理解。

  • 空间复杂度为 O(n)。

• 优化后的代码：

  • 使用滚动数组优化，空间复杂度降低到 O(1)。

  • 适合对空间复杂度有要求的场景。

三、 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

解法一：算法代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();// 初始化 dp 表，大小为 n + 1vector<int> dp(n + 1, 0);// 初始化dp[0] = 0; // 从第 0 阶开始不需要花费dp[1] = 0; // 从第 1 阶开始不需要花费// 填表for (int i = 2; i < n + 1; i++) {// 状态转移方程dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2]);}// 返回结果return dp[n];}
};

        这段代码解决的问题是：最小花费爬楼梯。给定一个数组 cost，其中 cost[i] 表示从第 i 阶楼梯向上爬需要的花费。每次可以爬 1 步或 2 步，求爬到楼梯顶部的最小花费。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

   • 假设有 n 阶楼梯，每阶楼梯有一个对应的花费 cost[i]。

   • 每次可以爬 1 步或 2 步。

   • 求从第 0 阶或第 1 阶开始，爬到楼梯顶部的最小花费。

2. 动态规划定义：

   • 定义 dp[i] 表示爬到第 i 阶楼梯的最小花费。

   • 状态转移方程：

     • dp[i] = min(cost[i-1] + dp[i-1], cost[i-2] + dp[i-2])

     • 因为可以从第 i-1 阶爬 1 步，或者从第 i-2 阶爬 2 步。

3. 边界条件：

   • dp[0] = 0：从第 0 阶开始不需要花费。

   • dp[1] = 0：从第 1 阶开始不需要花费。

4. 填表过程：

   • 从 i = 2 开始，逐个计算 dp[i]，直到 i = n。

   • 每次计算 dp[i] 时，选择从 i-1 阶爬 1 步或从 i-2 阶爬 2 步的最小花费。

5. 返回结果：

   • 最终返回 dp[n]，即爬到第 n 阶楼梯的最小花费。

---

代码优化思路

1. 空间优化：

   • 当前代码使用了一个大小为 n + 1 的数组 dp，空间复杂度为 O(n)。

   • 由于每次计算 dp[i] 只需要前两个值，可以用滚动数组优化，将空间复杂度降低到 O(1)。

2. 滚动数组优化：

   • 使用两个变量 a 和 b 分别表示 dp[i-2] 和 dp[i-1]。

   • 每次计算当前值 c = min(cost[i-1] + b, cost[i-2] + a)，然后更新 a = b, b = c。

---

优化后的代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();// 使用滚动数组优化int a = 0; // 表示 dp[i-2]int b = 0; // 表示 dp[i-1]int c = 0; // 表示 dp[i]// 填表for (int i = 2; i < n + 1; i++) {// 状态转移方程c = min(cost[i - 1] + b, cost[i - 2] + a);// 更新 a 和 ba = b;b = c;}// 返回结果return c;}
};

---

优化后的代码分析

1. 空间复杂度：

   • 从 O(n) 降低到 O(1)，只使用了常数个变量。

2. 时间复杂度：

   • 仍然是 O(n)，因为需要遍历从 2 到 n 的所有数。

3. 边界条件处理：

   • 当 n 为 0 或 1 时，直接返回 0，避免了不必要的计算。

---

总结

• 原始代码：

  • 使用动态规划数组存储中间结果，适合初学者理解。

  • 空间复杂度为 O(n)。

• 优化后的代码：

  • 使用滚动数组优化，空间复杂度降低到 O(1)。

  • 适合对空间复杂度有要求的场景。

解法二：算法代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();// 创建 dp 表，大小为 nvector<int> dp(n);// 初始化dp[n - 1] = cost[n - 1]; // 从第 n-1 阶开始的花费dp[n - 2] = cost[n - 2]; // 从第 n-2 阶开始的花费// 填表（从后向前）for (int i = n - 3; i >= 0; i--) {dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i];}// 返回结果return min(dp[0], dp[1]);}
};

        这段代码解决的问题是：最小花费爬楼梯。与之前的代码不同，这段代码采用了从后向前填表的动态规划思路。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

   • 给定一个数组 cost，其中 cost[i] 表示从第 i 阶楼梯向上爬需要的花费。

   • 每次可以爬 1 步或 2 步。

   • 求从第 0 阶或第 1 阶开始，爬到楼梯顶部的最小花费。

2. 动态规划定义：

   • 定义 dp[i] 表示从第 i 阶楼梯开始，爬到楼梯顶部的最小花费。

   • 状态转移方程：

     • dp[i] = min(dp[i+1], dp[i+2]) + cost[i]

     • 因为可以从第 i 阶爬 1 步到第 i+1 阶，或者爬 2 步到第 i+2 阶。

3. 边界条件：

   • dp[n-1] = cost[n-1]：从第 n-1 阶开始，只能爬 1 步到顶部，花费为 cost[n-1]。

   • dp[n-2] = cost[n-2]：从第 n-2 阶开始，可以选择爬 1 步或 2 步，花费为 cost[n-2]。

4. 填表过程：

   • 从 i = n-3 开始，向前逐个计算 dp[i]，直到 i = 0。

   • 每次计算 dp[i] 时，选择从 i+1 阶爬 1 步或从 i+2 阶爬 2 步的最小花费，并加上当前阶的花费 cost[i]。

5. 返回结果：

   • 最终返回 min(dp[0], dp[1])，即从第 0 阶或第 1 阶开始的最小花费。

---

代码优化思路

1. 空间优化：

   • 当前代码使用了一个大小为 n 的数组 dp，空间复杂度为 O(n)。

   • 由于每次计算 dp[i] 只需要后两个值，可以用滚动数组优化，将空间复杂度降低到 O(1)。

2. 滚动数组优化：

   • 使用两个变量 a 和 b 分别表示 dp[i+1] 和 dp[i+2]。

   • 每次计算当前值 c = min(a, b) + cost[i]，然后更新 a = b, b = c。

---

优化后的代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();// 使用滚动数组优化int a = cost[n - 1]; // 表示 dp[i+1]int b = cost[n - 2]; // 表示 dp[i+2]int c = 0; // 表示 dp[i]// 填表（从后向前）for (int i = n - 3; i >= 0; i--) {c = min(a, b) + cost[i];// 更新 a 和 ba = b;b = c;}// 返回结果return min(a, b);}
};

---

优化后的代码分析

1. 空间复杂度：

   • 从 O(n) 降低到 O(1)，只使用了常数个变量。

2. 时间复杂度：

   • 仍然是 O(n)，因为需要遍历从 n-3 到 0 的所有数。

3. 边界条件处理：

   • 当 n 为 0 或 1 时，直接返回 0，避免了不必要的计算。

---

总结

• 原始代码：

  • 使用动态规划数组存储中间结果，适合初学者理解。

  • 空间复杂度为 O(n)。

• 优化后的代码：

  • 使用滚动数组优化，空间复杂度降低到 O(1)。

  • 适合对空间复杂度有要求的场景。

 四、91. 解码方法 - 力扣（LeetCode）

方法一：算法代码（直接初始化）

class Solution {
public:int numDecodings(string s) {int n = s.size();// 创建 dp 表，大小为 nvector<int> dp(n);// 初始化第一个位置dp[0] = (s[0] != '0') ? 1 : 0; // 如果第一个字符不是 '0'，则有一种解码方式// 处理边界情况if (n == 1)return dp[0];// 初始化第二个位置if (s[1] >= '1' && s[1] <= '9')dp[1] += dp[0]; // 如果第二个字符可以单独解码int t = (s[0] - '0') * 10 + (s[1] - '0');if (t >= 10 && t <= 26)dp[1] += 1; // 如果前两个字符可以联合解码// 填表for (int i = 2; i < n; i++) {// 如果当前字符可以单独解码if (s[i] >= '1' && s[i] <= '9')dp[i] += dp[i - 1];// 如果当前字符和前一个字符可以联合解码int t = (s[i - 1] - '0') * 10 + (s[i] - '0');if (t >= 10 && t <= 26)dp[i] += dp[i - 2];}// 返回结果return dp[n - 1];}
};

        这段代码解决的问题是：解码方法的总数。给定一个由数字组成的字符串 s，将其解码成字母（A 到 Z），其中 A 对应 1，B 对应 2，...，Z 对应 26。要求计算所有可能的解码方式的总数。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

   • 给定一个字符串 s，其中每个字符是数字（0 到 9）。

   • 将字符串解码成字母，1 对应 A，2 对应 B，...，26 对应 Z。

   • 求所有可能的解码方式的总数。

2. 动态规划定义：

   • 定义 dp[i] 表示字符串 s 的前 i 个字符的解码方式总数。

   • 状态转移方程：

     • 如果 s[i] 可以单独解码（即 s[i] 不是 0），则 dp[i] += dp[i-1]。

     • 如果 s[i-1] 和 s[i] 可以联合解码（即 10 <= t <= 26，其中 t = (s[i-1] - '0') * 10 + (s[i] - '0')），则 dp[i] += dp[i-2]。

3. 边界条件：

   • dp[0]：表示空字符串的解码方式数，通常为 1（表示一种空解码方式）。

   • dp[1]：表示第一个字符的解码方式数，如果 s[0] 不是 0，则 dp[1] = 1，否则 dp[1] = 0。

4. 填表过程：

   • 从 i = 2 开始，逐个计算 dp[i]，直到 i = n-1。

   • 每次计算 dp[i] 时，检查当前字符是否可以单独解码，以及是否可以与前一个字符联合解码。

5. 返回结果：

   • 最终返回 dp[n-1]，即整个字符串的解码方式总数。

---

问题：

        在这段代码中，dp 表定义为 n 的大小（即 vector<int> dp(n)），而不是 n + 1，是因为这段代码的动态规划定义和填表逻辑与之前的代码有所不同。以下是详细的解释：

1. 动态规划定义

在这段代码中，dp[i] 的定义是：字符串 s 的前 i + 1 个字符的解码方式总数。
换句话说：

• dp[i] 表示字符串 s 从下标 0 到下标 i 的解码方式数。

• 最终结果是 dp[n - 1]，即整个字符串的解码方式数。

---

2. 为什么 dp 表大小为 n

• 下标范围：

  • 字符串 s 的下标范围是 0 到 n-1。

  • dp[i] 表示从第 0 个字符到第 i 个字符的解码方式数，因此 dp 表的下标范围也是 0 到 n-1。

  • 如果定义为 n + 1，则会多出一个无用的位置 dp[n]，因为字符串的下标最多到 n-1。

• 逻辑一致性：

  • 这段代码的填表逻辑是从左到右，逐个计算 dp[i]。

  • dp[i] 的值依赖于 dp[i-1] 和 dp[i-2]，因此只需要 n 个位置来存储中间结果。

---

3. 代码的具体逻辑

1. 初始化：

   • dp[0]：表示第一个字符的解码方式数。如果 s[0] 不是 0，则 dp[0] = 1，否则 dp[0] = 0。

   • dp[1]：表示前两个字符的解码方式数。如果 s[1] 可以单独解码，则 dp[1] += dp[0]；如果 s[0] 和 s[1] 可以联合解码，则 dp[1] += 1。

2. 填表：

   • 从 i = 2 开始，逐个计算 dp[i]：

     • 如果 s[i] 可以单独解码（即 s[i] 不是 0），则 dp[i] += dp[i-1]。

     • 如果 s[i-1] 和 s[i] 可以联合解码（即 10 <= t <= 26，其中 t = (s[i-1] - '0') * 10 + (s[i] - '0')），则 dp[i] += dp[i-2]。

3. 返回结果：

   • 最终返回 dp[n-1]，即整个字符串的解码方式数。

---

4. 为什么不需要 n + 1 的大小

• dp[i] 的定义：

  • dp[i] 表示从第 0 个字符到第 i 个字符的解码方式数。

  • 因此，dp 表的下标范围是 0 到 n-1，正好对应字符串 s 的下标范围。

• 边界条件：

  • 当 n = 1 时，直接返回 dp[0]。

  • 当 n = 2 时，直接返回 dp[1]。

  • 不需要额外的 dp[n]，因为 dp[n-1] 已经表示整个字符串的解码方式数。

---

5. 与 n + 1 定义的对比

• n + 1 的定义：

  • 如果 dp 表定义为 n + 1，则 dp[i] 表示字符串 s 的前 i 个字符的解码方式数。

  • 此时，dp[0] 表示空字符串的解码方式数（通常为 1），dp[1] 表示第一个字符的解码方式数，依此类推。

  • 最终结果是 dp[n]，即整个字符串的解码方式数。

• n 的定义：

  • 如果 dp 表定义为 n，则 dp[i] 表示字符串 s 的前 i + 1 个字符的解码方式数。

  • 此时，dp[0] 表示第一个字符的解码方式数，dp[1] 表示前两个字符的解码方式数，依此类推。

  • 最终结果是 dp[n-1]，即整个字符串的解码方式数。

---

6. 总结

• dp 表定义为 n 的原因：

  • dp[i] 表示字符串 s 的前 i + 1 个字符的解码方式数。

  • dp 表的下标范围是 0 到 n-1，正好对应字符串 s 的下标范围。

  • 不需要额外的 dp[n]，因为 dp[n-1] 已经表示整个字符串的解码方式数。

• 与 n + 1 定义的区别：

  • n + 1 的定义中，dp[i] 表示前 i 个字符的解码方式数，需要额外的 dp[0] 表示空字符串。

  • n 的定义中，dp[i] 表示前 i + 1 个字符的解码方式数，逻辑更直接。

        根据具体需求，可以选择使用 n 或 n + 1 的定义。这段代码使用 n 的定义，逻辑清晰且节省空间。

---

代码优化思路

1. 空间优化：

   • 当前代码使用了一个大小为 n 的数组 dp，空间复杂度为 O(n)。

   • 由于每次计算 dp[i] 只需要前两个值，可以用滚动数组优化，将空间复杂度降低到 O(1)。

2. 滚动数组优化：

   • 使用三个变量 a, b, c 分别表示 dp[i-2], dp[i-1], dp[i]。

   • 每次计算当前值 c，然后更新 a = b, b = c。

---

优化后的代码

class Solution {
public:int numDecodings(string s) {int n = s.size();// 处理空字符串if (n == 0)return 0;// 使用滚动数组优化int a = 1; // 表示 dp[i-2]int b = (s[0] != '0') ? 1 : 0; // 表示 dp[i-1]int c = 0; // 表示 dp[i]// 填表for (int i = 1; i < n; i++) {c = 0; // 重置当前值// 如果当前字符可以单独解码if (s[i] >= '1' && s[i] <= '9')c += b;// 如果当前字符和前一个字符可以联合解码int t = (s[i - 1] - '0') * 10 + (s[i] - '0');if (t >= 10 && t <= 26)c += a;// 更新 a 和 ba = b;b = c;}// 返回结果return b;}
};

---

优化后的代码分析

1. 空间复杂度：

   • 从 O(n) 降低到 O(1)，只使用了常数个变量。

2. 时间复杂度：

   • 仍然是 O(n)，因为需要遍历整个字符串。

3. 边界条件处理：

   • 当 n 为 0 时，直接返回 0。

   • 当 n 为 1 时，直接返回 b 的初始值。

---

总结

• 原始代码：

  • 使用动态规划数组存储中间结果，适合初学者理解。

  • 空间复杂度为 O(n)。

• 优化后的代码：

  • 使用滚动数组优化，空间复杂度降低到 O(1)。

  • 适合对空间复杂度有要求的场景。

 

方法二：算法代码（添加辅助位置初始化）

class Solution {
public:int numDecodings(string s) {int n = s.size();// 创建 dp 表，大小为 n + 1vector<int> dp(n + 1);// 初始化dp[0] = 1; // 空字符串的解码方式数为 1dp[1] = (s[0] != '0') ? 1 : 0; // 第一个字符的解码方式数// 填表for (int i = 2; i <= n; i++) {// 如果当前字符可以单独解码if (s[i - 1] != '0')dp[i] += dp[i - 1];// 如果当前字符和前一个字符可以联合解码int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if (t >= 10 && t <= 26)dp[i] += dp[i - 2];}// 返回结果return dp[n];}
};

         这段代码是对解码方法的总数问题的优化实现。与之前的代码相比，这段代码通过调整 dp 表的定义和初始化方式，使得逻辑更加简洁和清晰。以下是代码的思路分析：

---

代码思路分析

1. 问题定义：

   • 给定一个由数字组成的字符串 s，将其解码成字母（A 到 Z），其中 A 对应 1，B 对应 2，...，Z 对应 26。

   • 要求计算所有可能的解码方式的总数。

2. 动态规划定义：

   • 定义 dp[i] 表示字符串 s 的前 i 个字符的解码方式总数。

   • 状态转移方程：

     • 如果 s[i-1] 可以单独解码（即 s[i-1] 不是 0），则 dp[i] += dp[i-1]。

     • 如果 s[i-2] 和 s[i-1] 可以联合解码（即 10 <= t <= 26，其中 t = (s[i-2] - '0') * 10 + (s[i-1] - '0')），则 dp[i] += dp[i-2]。

3. 边界条件：

   • dp[0] = 1：表示空字符串的解码方式数为 1（这是一种虚拟的初始化，保证后续填表逻辑正确）。

   • dp[1]：表示第一个字符的解码方式数，如果 s[0] 不是 0，则 dp[1] = 1，否则 dp[1] = 0。

4. 填表过程：

   • 从 i = 2 开始，逐个计算 dp[i]，直到 i = n。

   • 每次计算 dp[i] 时，检查当前字符是否可以单独解码，以及是否可以与前一个字符联合解码。

5. 返回结果：

   • 最终返回 dp[n]，即整个字符串的解码方式总数。

---

代码优化思路

1. 空间优化：

   • 当前代码使用了一个大小为 n + 1 的数组 dp，空间复杂度为 O(n)。

   • 由于每次计算 dp[i] 只需要前两个值，可以用滚动数组优化，将空间复杂度降低到 O(1)。

2. 滚动数组优化：

   • 使用三个变量 a, b, c 分别表示 dp[i-2], dp[i-1], dp[i]。

   • 每次计算当前值 c，然后更新 a = b, b = c。

---

优化后的代码

class Solution {
public:int numDecodings(string s) {int n = s.size();// 处理空字符串if (n == 0)return 0;// 使用滚动数组优化int a = 1; // 表示 dp[i-2]int b = (s[0] != '0') ? 1 : 0; // 表示 dp[i-1]int c = 0; // 表示 dp[i]// 填表for (int i = 2; i <= n; i++) {c = 0; // 重置当前值// 如果当前字符可以单独解码if (s[i - 1] != '0')c += b;// 如果当前字符和前一个字符可以联合解码int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if (t >= 10 && t <= 26)c += a;// 更新 a 和 ba = b;b = c;}// 返回结果return b;}
};

---

优化后的代码分析

1. 空间复杂度：

   • 从 O(n) 降低到 O(1)，只使用了常数个变量。

2. 时间复杂度：

   • 仍然是 O(n)，因为需要遍历整个字符串。

3. 边界条件处理：

   • 当 n 为 0 时，直接返回 0。

   • 当 n 为 1 时，直接返回 b 的初始值。

---

总结

• 原始代码：

  • 使用动态规划数组存储中间结果，逻辑清晰，适合初学者理解。

  • 空间复杂度为 O(n)。

• 优化后的代码：

  • 使用滚动数组优化，空间复杂度降低到 O(1)。

  • 适合对空间复杂度有要求的场景。