h5网站制作一般多少钱,seo网站优化知识,高德地图有没有vr全景,网站框架方案本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1示例 2
输入coins [2], amount 3
输出-1示例 3
输入coins [1], amount 0
输出0示例 4
输入coins [1], amount 1
输出1示例 5
输入coins [1], amount 2
输出2提示
1 coins.length 121 coins[i] 2^31 - 10 amount 10^4
注意本题与主站 322 题相同 https://leetcode-cn.com/problems/coin-change/ 解法 完全背包恰好装满背包的最小问题
拿到动态规划问题后做以下几个步骤
分析是否为背包问题。 背包问题的判定——背包问题具备的特征给定一个 t a r g e t target target t a r g e t target target 可以是数字也可以是字符串再给定一个数组 n u m s nums nums n u m s nums nums 中装的可能是数字也可能是字符串问能否使用 n u m s nums nums 中的元素做各种排列组合得到 t a r g e t target target 。如果是背包问题那么是求组合数、True/False、最大最小三种背包问题中的哪一种。如果是求组合数问题是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法不需要考虑顺序又有对应的解法。再分为是0-1背包问题还是完全背包问题。也就是题目给的 n u m s nums nums 数组中的元素是否可以重复使用。
粗略一看本题是求装满背包的最小问题完全背包。套用模板
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, amount 1);for (int i 0; i coins.size(); i)for (int j coins[i]; j amount; j)dp[j] min(dp[j], dp[j - coins[i]] 1);return dp[amount] amount ? dp[amount] : -1;}
};
