两道算法练习

力扣322零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入： coins = [1, 2, 5], amount = 11 输出： 3 解释： 11 = 5 + 5 + 1

示例 2：

输入： coins = [2], amount = 3 输出： -1

示例 3：

输入： coins = [1], amount = 0 输出： 0

提示：

1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104 分析思路 分析子问题，当所有的子问题都是最优的时候总问题也就达到了最优。分析最终状态，以示例1为例子：在选到5的时候刚好满足金额等于amount同时数量最优分析去掉最后一个问题的状态： 它的子问题也就是：用最少得硬币数凑出 amount - 5可以发现这个问题可以像递归搜索树一样进行拆分又继续分析去掉倒数第二个问题的状态。 那么我们来分析代码： const int N = 10010; class Solution { int mem[N]; int dfs(vector<int>& coins, int amount) { if (mem[amount]) return mem[amount]; int res = 1e9; if (amount == 0) return 0; if (amount < 0) return 1e9; for (int i = 0; i < coins.size(); i++) { if (amount >= coins[i]) res = min(res, 1 + dfs(coins, amount - coins[i])); } mem[amount] = res; return res; } public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); int ans = dfs(coins, amount); return ans == 1e9 ? -1 : ans; } }; 我们的思路就是让它凑出的每一个amount之前的数值都满足最小硬币的需求，那么当它递推到amount的时候，它的每一个子问题都是最优的，那么总问题就是最优的了。 for (int i = 0; i < coins.size(); i++) { if (amount >= coins[i]) res = min(res, 1 + dfs(coins, amount - coins[i])); }

我们不断地往下搜索，直到amount被减到0，其中每一个分支都进行了min的处理，所以当从下往上回溯的时候，返回的就是每个分支就小的情况也是每个子问题最优的情况。

所以我们可以这样想dp： 我们从凑出1块2块3块…知道amount块钱，每一次我们都考虑凑出的硬币数量最少，那么当我们推到amount的时候，不就是最优了吗？

class Solution { public: int coinChange(vector<int>& coins, int amount) { if (amount == 0) return 0; int n = coins.size(); vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) dp[i] = min(dp[i], dp[i - coin] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; } }; dp数组中的每个元素都被初始化为比amount大的数字，我们每次都更新凑得钱数所需硬币的最小值，从1凑到amount，这样到了amount的时候，就是最优的答案了 leetcode 413

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

示例 1：

输入： nums = [1,2,3,4] 输出： 3 解释： nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入： nums = [1] 输出： 0

提示：

1 <= nums.length <= 5000-1000 <= nums[i] <= 1000

1. 重述问题：找出数组中所有等差子数组的数量包括它本身 2. 最后一步：

以第 i 个元素结尾的等差子数组数目，取决于当前差值是否与前一个差值相等。

如果相等，则以 i 结尾的数目等于以 i-1 结尾的数目加 1 3. 去掉最后一步，是否能划分出子问题：

子问题划分：

如果当前差值与前一个差值相等，则 dp[i] = dp[i-1] + 1。

否则，dp[i] = 0。

示例 1：

输入：nums = [1, 2, 3, 4]

我们需要找出所有长度至少为 3 的连续子数组，且这些子数组是等差数列。

子数组 [1, 2, 3]：差值为 1，是等差数列。

子数组 [2, 3, 4]：差值为 1，是等差数列。

子数组 [1, 2, 3, 4]：差值为 1，是等差数列。

总共有 3 个等差子数组。

---

示例 2：

输入：nums = [1, 3, 5, 7, 9]

子数组 [1, 3, 5]：差值为 2，是等差数列。

子数组 [3, 5, 7]：差值为 2，是等差数列。

子数组 [5, 7, 9]：差值为 2，是等差数列。

子数组 [1, 3, 5, 7]：差值为 2，是等差数列。

子数组 [3, 5, 7, 9]：差值为 2，是等差数列。

子数组 [1, 3, 5, 7, 9]：差值为 2，是等差数列。

总共有 6 个等差子数组。

---

表格分析

我们可以通过表格来记录以每个位置结尾的等差子数组的个数。假设 dp[i] 表示以第 i 个元素结尾的等差子数组的个数。

示例 1：nums = [1, 2, 3, 4] 索引 (i)元素值 (nums[i])差值 (nums[i] - nums[i-1])前一个差值 (nums[i-1] - nums[i-2])dp[i]（以 i 结尾的等差子数组个数）解释01--0长度不足 3，无法形成等差子数组。121-0长度不足 3，无法形成等差子数组。23111差值相等，形成一个新的等差子数组 [1, 2, 3]。34112差值相等，形成一个新的等差子数组 [2, 3, 4]，并扩展 [1, 2, 3, 4]。

最终结果：dp[2] + dp[3] = 1 + 2 = 3。

---

示例 2：nums = [1, 3, 5, 7, 9] 索引 (i)元素值 (nums[i])差值 (nums[i] - nums[i-1])前一个差值 (nums[i-1] - nums[i-2])dp[i]（以 i 结尾的等差子数组个数）解释01--0长度不足 3，无法形成等差子数组。132-0长度不足 3，无法形成等差子数组。25221差值相等，形成一个新的等差子数组 [1, 3, 5]。37222差值相等，形成一个新的等差子数组 [3, 5, 7]，并扩展 [1, 3, 5, 7]。49223差值相等，形成一个新的等差子数组 [5, 7, 9]，并扩展 [3, 5, 7, 9] 和 [1, 3, 5, 7, 9]。

最终结果：dp[2] + dp[3] + dp[4] = 1 + 2 + 3 = 6。

if (diff == prev_diff) { return helper(i-1, nums) + 1; } else { return 0; } 举例说明 示例：nums = [1, 2, 3, 4]

当 i = 2 时：

当前元素：nums[2] = 3

差值：diff = nums[2] - nums[1] = 3 - 2 = 1

前一个差值：prev_diff = nums[1] - nums[0] = 2 - 1 = 1

判断：diff == prev_diff 成立。

递归调用：helper(1, nums)，由于 i = 1 不满足条件，返回 0。

结果：helper(2, nums) = helper(1, nums) + 1 = 0 + 1 = 1。

表示以 nums[2] 结尾的等差子数组有 1 个，即 [1, 2, 3]。

当 i = 3 时：

当前元素：nums[3] = 4

差值：diff = nums[3] - nums[2] = 4 - 3 = 1

前一个差值：prev_diff = nums[2] - nums[1] = 3 - 2 = 1

判断：diff == prev_diff 成立。

递归调用：helper(2, nums) = 1。

结果：helper(3, nums) = helper(2, nums) + 1 = 1 + 1 = 2。

表示以 nums[3] 结尾的等差子数组有 2 个：

[2, 3, 4]

[1, 2, 3, 4]

const int N = 10010; class Solution { public: //x表示当前以nums[x]为结尾的数组 int dfs(int x, vector<int>& nums) { if (x < 2) return 0; if (mem[x]) return mem[x]; int diff = nums[x] - nums[x - 1]; int prv_diff = nums[x - 1] - nums[x - 2]; if (diff == prv_diff) { return mem[x] = dfs(x - 1, nums) + 1; } else { return 0; } } int mem[N]; int numberOfArithmeticSlices(vector<int> &nums) { int n = nums.size(); if (nums.size() < 3) return 0; // vector<int> dp(n, 0); int res = 0; int prev = 0; // for (int i = 2; i < nums.size(); i++) // { // res += dfs(i, nums); // } // return res; for (int i = 2; i < nums.size(); i++) { if (nums[i] - nums[i - 1] == nums[i - 1]- nums[i - 2]) { // dp[i] = dp[i - 1] + 1; prev = prev + 1; res += prev; } } return prev; } };