第42天-DP-第九章● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数

这篇具有很好参考价值的文章主要介绍了第42天-DP-第九章● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 爬楼梯(完全背包方式实现)

- LeetCode链接

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        int m = 2;
        // 本题的结果中,不同的排序方式也属于不同的结果
        for(int i=1; i<=n; i++){       // 先遍历背包(当前是第几个台阶)
            for(int j=1; j<=m; j++){     
                if(i - j >= 0){          // 
                    dp[i] += dp[i-j];
                }
            }
        }

        return dp[n];
    }
};

2. 零钱兑换 (要求最少的个数)

- LeetCode链接

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 求的是组成amount 最少的硬币的数量
        vector<int> 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] = min(dp[j], dp[j-coins[i]]+1);
                }
            }
        }

        if(dp[amount] == INT_MAX) return -1;

        return dp[amount];
    }
};

3. 完全平方数

- LeetCode链接

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。=
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11

自己第一次做错了文章来源地址https://www.toymoban.com/news/detail-429592.html

class Solution {
public:
    int numSquares(int n) {

        // 如果n==1这里需要额外判断
        vector<int> val(n/2+2, 0);
        val[1] = 1;
        for(int i=1; i<=n/2; i++){
            val[i] = i*i;
        }

        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;

        // 先遍历背包数,再遍历数组
        for(int i=1; i<val.size(); i++){
            for(int j=val[i]; j<=n; j++){
                if(i > n){ break;}
                dp[j] = min(dp[j], dp[j-val[i]]+1);
            }
        }

        return dp[n];

    }
};
class Solution {
public:
    int numSquares(int n) {
        vector<int> 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], dp[j-i*i]+1);
            }
        }
        return dp[n];

    }
};

到了这里,关于第42天-DP-第九章● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法打卡day39|动态规划篇07| Leetcode 70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数

    Leetcode 70. 爬楼梯(进阶版) 题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,

    2024年04月14日
    浏览(65)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(59)
  • day 45:爬楼梯进阶版;322. 零钱兑换;279. 完全平方数

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢? dp[j]:爬到j层一共有多少种方法。 递推公式:dp[j] += dp[j - i]; dp[0] = 1; dp[i]:目标整数为i的背包所能凑的最少硬币

    2024年02月07日
    浏览(93)
  • 【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 (day38补)

    斐波那契数  (通常用  F(n) 表示)形成的序列称为 斐波那契数列 。该数列由  0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: 给定  n ,请计算 F(n) 。 示例 1: 示例 2: 示例 3: 提示: 0 = n = 30 斐波那契数列大家应该非常熟悉不过了,非常适合作为动规第

    2024年02月07日
    浏览(45)
  • 【LeetCode题目详解】第九章 动态规划part06 完全背的讲解 518. 零钱兑换 II 377. 组合总和 Ⅳ (day44补)

    # 完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品都有无限个(也就是可以放入背包多次) ,求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。

    2024年02月09日
    浏览(35)
  • 【Day45】代码随想录之动态规划part7—爬楼梯(进阶)、零钱兑换、完全平方数

    今天又是补打卡的一天,开冲!!! 今日任务: 70.爬楼梯(进阶) 322.零钱兑换 279.完全平方数 这道题之前做过一次,但是可以采用完全背包的问题来分析一遍。 卡玛网题目:【57.爬楼梯】 这个题目其实是更难了一点,因为前面的题目都是每次要不爬1阶楼梯,要不爬2阶楼

    2024年03月25日
    浏览(52)
  • leetcode322:零钱兑换

    leetcode322:零钱兑换 题目: 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 思路:动态规划

    2024年02月12日
    浏览(35)
  • 力扣 | 322. 零钱兑换

    这里使用动态规划,代码简洁更易理解

    2024年01月21日
    浏览(39)
  • leetcode 322. 零钱兑换

             本题属于完全背包问题,但要求最少的硬币个数。于是设定dp数组的含义dp[i]:总金额为i时,能凑成i的最少硬币个数。  需要注意初始化dp数组时,除0以外的其他地方需要初始化为INT_MAX以保证在递推过程中能被正确的覆盖。           代码如下:         ps:本题

    2024年02月12日
    浏览(31)
  • 【动态规划】322. 零钱兑换

    定义 要凑出金额n 至少要dp(coins,n)个硬币 确定base case 目标金额为0 返回0 确定 状态 也就是原问题和子问题中的变量,你每次抽取一个硬币,都会导致目标金额减少,所以状态就是目标金额 确定选择,也就是导致状态产生变化的行为,每次选一个硬币都会导致目标金额的减少

    2024年02月10日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包