两道算法练习
力扣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 结尾的等差子数组个数） | 解释 |
|---|---|---|---|---|---|
| 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]
-
当
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;}
};