两道算法练习

力扣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 <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= 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.
  去掉最后一步，是否能划分出子问题：

1. 子问题划分：

   • 如果当前差值与前一个差值相等，则 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 结尾的等差子数组个数）	解释
0	1	-	-	0	长度不足 3，无法形成等差子数组。
1	2	1	-	0	长度不足 3，无法形成等差子数组。
2	3	1	1	1	差值相等，形成一个新的等差子数组 [1, 2, 3]。
3	4	1	1	2	差值相等，形成一个新的等差子数组 [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 结尾的等差子数组个数）	解释
0	1	-	-	0	长度不足 3，无法形成等差子数组。
1	3	2	-	0	长度不足 3，无法形成等差子数组。
2	5	2	2	1	差值相等，形成一个新的等差子数组 [1, 3, 5]。
3	7	2	2	2	差值相等，形成一个新的等差子数组 [3, 5, 7]，并扩展 [1, 3, 5, 7]。
4	9	2	2	3	差值相等，形成一个新的等差子数组 [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]

1. 当 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]。

2. 当 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;}
};