力扣题解(零钱兑换II)

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

思路:

对一堆数字中选取某几个,且每个数字可以重复出现,因此是完全背包问题。

dp[i][j]表示前i个字符组合是j的所有组合数。

dp[i][j]=dp[i-1][j]+dp[i][j-coins[i]]。(此处用+的原因是要求的是所有可能的组合数)

初始化:

i为0的时候,仅有j同样为0才有可能有组合数,因此其余均为0.

当j为0的时候,对i任意取值,都存在一个数都不取结果为0的情况,因此dp[i][0]为1.

class Solution {
public:
    int change(int amount, vector<int>& coins) {
      int n=coins.size();
     int INF=0x3f3f3f3f;
     vector<vector<int>>dp(n+1,vector<int>(amount+1,0));
     for(int i=0;i<=n;i++)
     {
        dp[i][0]=1;
     }
     coins.insert(coins.begin(),0);
     for(int i=1;i<=n;i++)
     {
        for(int j=1;j<=amount;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(j-coins[i]>=0)
            {
              //  cout<<i<<j-coins[i]<<" ||";
            
              dp[i][j]+=dp[i][j-coins[i]];
            
            }
        }
     }
     return dp[n][amount]==INF?0:dp[n][amount];


    }
    
};

相关推荐

  1. 题解零钱兑换II

    2024-07-21 04:02:02       36 阅读
  2. 322. 零钱兑换

    2024-07-21 04:02:02       59 阅读
  3. 零钱兑换零钱兑换2,动态规划算法

    2024-07-21 04:02:02       49 阅读
  4. 518. 零钱兑换 II

    2024-07-21 04:02:02       50 阅读
  5. LeetCode-零钱兑换II

    2024-07-21 04:02:02       45 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 04:02:02       172 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 04:02:02       190 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 04:02:02       158 阅读
  4. Python语言-面向对象

    2024-07-21 04:02:02       171 阅读

热门阅读

  1. Python学习-九大数据类型整合,详细讲解

    2024-07-21 04:02:02       35 阅读
  2. web前端 Vue 框架面试120题(三)

    2024-07-21 04:02:02       32 阅读
  3. 【C++】位运算与相关算法问题

    2024-07-21 04:02:02       37 阅读
  4. Vue Router的路由正则表达式

    2024-07-21 04:02:02       32 阅读
  5. C++编程:实现一个跨平台安全的定时器Timer模块

    2024-07-21 04:02:02       34 阅读
  6. CSS中object-fit: cover;

    2024-07-21 04:02:02       34 阅读
  7. Git使用

    2024-07-21 04:02:02       37 阅读
  8. 推荐收藏!Python Flask 项目生产环境部署指南

    2024-07-21 04:02:02       36 阅读
  9. 对androidTestDebug 产物进行重新签名

    2024-07-21 04:02:02       32 阅读