宁海县城镇建设局网站,建官网公司,反馈网站制作,官方网站入口力扣322零钱兑换
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种硬币的…力扣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(vectorint 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(vectorint 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(vectorint coins, int amount) {if (amount 0)return 0;int n coins.size();vectorint 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 个元素结尾的等差子数组的个数。
示例 1nums [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。 示例 2nums [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, vectorint 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(vectorint nums){int n nums.size();if (nums.size() 3)return 0;// vectorint 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;}
};
