力扣完全平方数279和力扣91解码方法的做题笔记

力扣279完全平方数 思路

1.**重述问题:

给你一个数字n，拆分出它的平方数要求和为n，且这些平方数的个数要最少

给定一个整数 n，找到最少数量的完全平方数，使得它们的和等于 n。 2.**找出问题的最后一步:

找到以4为结尾的平方数恰好满足4 + 4 + 4 = 12，且最少

假设最后一步选择了一个完全平方数 k²，那么问题转化为：找到和为 n - k² 的最少完全平方数。 3.**划分子问题:

找到以4为结尾最少的平方数组合，恰好满足12 - 4

对于每个 i（从 1 到 n），我们需要找到所有可能的 k²（k² <= i），然后递归求解 i - k² 的最少完全平方数。 4.**边界问题:

考虑和不能大于n

当 i = 0 时，不需要任何完全平方数，返回 0。

当 i 本身是一个完全平方数时，直接返回 1。

dfs + 记忆化搜索

const int N = 100010; class Solution { public: int mem[N]; int dfs(int n) { int res = 1e9; if (n == 0) return 0; if (mem[n]) return mem[n]; for (int i = 1; i * i <= n; i++) { res = min(res, dfs(n - i * i) + 1); } return mem[n] = res; } int numSquares(int n) { if (n == 0) { return 0; } int ans = dfs(n); return ans; } }; dp class Solution { public: int numSquares(int n) { if (n == 0) { return 0; } vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j * j <= i; j++) { dp[i] = min(dp[i], 1 + dp[i - j * j]); } } return dp[n]; } }; 力扣91解码方法 思路

1.**重述问题:

给你一个数字字符串，找出它所有能支持的编码，前缀0的是非法给定一个数字字符串 s，每个数字或两个数字的组合可以解码为字母（1→A，2→B，…，26→Z）。要求计算所有可能的解码方式总数。如果字符串中包含前导零（如 “06”）或无法解码的情况，返回 0。 2.**找出问题的最后一步:以226为例子，最后一步为 2 B 2B 6F ，最终问题是每一个字符单独成为编码对于字符串 s，解码的最后一步有两种可能：

单独解码最后一个字符：如果最后一个字符是 1 到 9，则可以单独解码为一个字母。

解码最后两个字符：如果最后两个字符组成的数字在 10 到 26 之间，则可以解码为一个字母。

例如，对于 s = "226"：

最后一步可以是 6 → F，此时问题转化为解码 "22"。

最后一步也可以是 26 → Z，此时问题转化为解码 "2"。 3.**划分子问题:

前一个问题就是22V 6F，那么子问题可划分为k个字符为一个编码？

根据最后一步的两种可能，可以将问题划分为两个子问题：

解码前 n-1 个字符：如果最后一个字符可以单独解码。

解码前 n-2 个字符：如果最后两个字符可以组合解码。

例如，对于 s = "226"：

子问题 1：解码 "22"。

子问题 2：解码 "2"。 4.**边界问题:

空字符串：如果字符串为空，只有一种解码方式（即空字符串本身）。

单个字符：

如果字符是 0，无法解码，返回 0。

如果字符是 1 到 9，可以解码，返回 1。

前导零：如果字符串以 0 开头（如 "06"），无法解码，返回 0。

无效组合：如果两个字符组成的数字不在 10 到 26 之间（如 "27"），则不能组合解码。

const int N = 10010; class Solution { public: int mem[N]; int dfs(string &s, int x) { int n = s.size(); if (n == x) return 1; if (s[x] == '0') return 0; if (mem[x]) return mem[x]; // 单个解码 int res = dfs(s, x + 1); // 两个解码 if (x + 1 < n) { int two = ((s[x] - '0') * 10) + (s[x + 1] - '0'); if (two >= 10 && two <= 26) { res += dfs(s, x + 2); } } return mem[x] = res; } int numDecodings(string s) { int res = 0; int n = s.size(); if (n == 0 || s[0] == '0') return 0; // vector<int> dp(n + 1, 0); // dp[0] = 1; // dp[1] = s[0] != '0' ? 1 : 0; int prevPrev = 1; int prev = s[0] != '0' ? 1 : 0; for (int i = 2; i <= n; i++) { int cur = 0; if (s[i - 1] != '0') cur += prev; // dp[i] += dp[i - 1]; int two = ((s[i - 2] - '0') * 10) + (s[i - 1] - '0'); if (two >= 10 && two <= 26) { // dp[i] += dp[i - 2]; cur += prevPrev; } prevPrev = prev; prev = cur; } return prev; // return dp[n]; } }; 做题中我遇到的问题 为什么是i - 1而不是i呢 1. 动态规划的状态定义

在动态规划中，我们通常定义：

dp[i]：表示前 i 个字符的解码方式数。

例如，dp[1] 表示前 1 个字符的解码方式数。

dp[2] 表示前 2 个字符的解码方式数。

以此类推。

---

2. 字符串的索引

在 C++ 中，字符串的索引是从 0 开始的。

例如，字符串 s = "226"：

s[0] = '2'。

s[1] = '2'。

s[2] = '6'。

---

3. 为什么用 s[i - 1] 而不是 s[i]？

dp[i] 表示前 i 个字符的解码方式数：

前 i 个字符对应字符串中的 s[0] 到 s[i - 1]。

因此，dp[i] 的解码方式数依赖于 s[i - 1]（当前字符）和 s[i - 2]（前一个字符）。

举例说明：

对于字符串 s = "226"：

dp[1] 表示前 1 个字符 '2' 的解码方式数。

dp[2] 表示前 2 个字符 "22" 的解码方式数。

dp[3] 表示前 3 个字符 "226" 的解码方式数。

---

4. 代码逻辑

在代码中，dp[i] 的解码方式数由两部分组成：

单独解码当前字符：

如果当前字符 s[i - 1] 不是 '0'，则可以单独解码。

此时，dp[i] += dp[i - 1]，表示前 i - 1 个字符的解码方式数。

组合解码两个字符：

如果当前字符 s[i - 1] 和前一个字符 s[i - 2] 可以组合解码（即组成的数字在 10 到 26 之间），则可以组合解码。

此时，dp[i] += dp[i - 2]，表示前 i - 2 个字符的解码方式数。

---

5. 示例分析 示例：s = "226"

初始化：

dp[0] = 1（空字符串）。

dp[1] = 1（'2' 可以单独解码）。

状态转移：

is[i-1]单独解码 (dp[i] += dp[i-1])组合解码 (dp[i] += dp[i-2])dp[i]2'2'dp[2] += dp[1] = 1two = 22，dp[2] += dp[0] = 123'6'dp[3] += dp[2] = 2two = 26，dp[3] += dp[1] = 13 最终结果：dp[3] = 3。

---

6. 为什么不用 s[i]？

如果使用 s[i]，会导致索引越界或逻辑错误：

对于 i = 1，s[1] 是第二个字符，而 dp[1] 表示前 1 个字符的解码方式数。

这样会导致状态转移的逻辑混乱，无法正确计算解码方式数。

---

7. 总结

dp[i] 表示前 i 个字符的解码方式数，因此当前字符是 s[i - 1]。

s[i - 1] 是当前字符，s[i - 2] 是前一个字符。

这种设计保证了状态转移的正确性和逻辑清晰性。