自学网站免费,公众号开发价钱,想学企业管理课程,wordpress站点版权设置leetcode 70. 爬楼梯 题目链接#xff1a;70. 爬楼梯 - 力扣#xff08;LeetCode#xff09; 本题可以用背包问题来解决#xff0c;就相当于楼顶是背包#xff0c;台阶是物品#xff0c;相当于之前写法的进阶版。
代码实现
class Solution {
public:int climbStairs(in… leetcode 70. 爬楼梯 题目链接70. 爬楼梯 - 力扣LeetCode 本题可以用背包问题来解决就相当于楼顶是背包台阶是物品相当于之前写法的进阶版。
代码实现
class Solution {
public:int climbStairs(int n) {vectorint dp(n 1,0);dp[0] 1;for(int i 1;i n;i) {for(int j 1;j 2;j) {if(i - j 0) dp[i] dp[i - j];}}return dp[n];}
}; leetcode 322. 零钱兑换 题目链接322. 零钱兑换 - 力扣LeetCode 视频链接动态规划之完全背包装满背包最少的物品件数是多少| LeetCode322.零钱兑换_哔哩哔哩_bilibili 题目概述
给你一个整数数组 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.确定dp数组含义dp[j]凑足总额为j所需钱币的最少个数为dp[j]。
2.确定递推公式dp[j] min(dp[j - coins[i]] 1, dp[j])。
3.数组初始化dp[0]0,非0下标初始化成最大值。以前都是max这次是min
4.确定遍历顺序本题不用强调顺序本题既不是组合数也不是排列数第一层遍历物品和背包哪个都行第二层也是。
5.打印dp数组 代码实现先物品后背包
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包if (dp[j - coins[i]] ! INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过dp[j] min(dp[j - coins[i]] 1, dp[j]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
};
代码实现先背包后物品
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for (int i 1; i amount; i) { // 遍历背包for (int j 0; j coins.size(); j) { // 遍历物品if (i - coins[j] 0 dp[i - coins[j]] ! INT_MAX ) {dp[i] min(dp[i - coins[j]] 1, dp[i]);}}}if (dp[amount] INT_MAX) return -1;return dp[amount];}
}; leetcode 279.完全平方数 题目链接279. 完全平方数 - 力扣LeetCode 视频链接动态规划之完全背包换汤不换药| LeetCode279.完全平方数_哔哩哔哩_bilibili 题目概述
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 示例 1
输入n 12
输出3
解释12 4 4 4
示例 2
输入n 13
输出2
解释13 4 9本题和上一道题其实都差不多换汤不换药的的东西。
代码实现先物品后背包
class Solution {
public:int numSquares(int n) {vectorint dp(n 1,INT_MAX);dp[0] 0;for(int i 1;i * i n;i) {for(int j i * i;j n;j) {dp[j] min(dp[j - i * i] 1,dp[j]);}}return dp[n];}
};
代码实现先背包后物品
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};
