leetocde 518 零钱兑换II

野性酷女 2022-09-16 15:19 124阅读 0赞

## 前言 ##

题目：[518. 零钱兑换 II][518. _ II]

参考：[完全背包问题-大草][-]、[零钱兑换 II-力扣官方题解][II-]

--------------------

## 提交代码 ##

我可以理解01背包的滚动数组，但是我理解不了完全背包的滚动数组。

理解不了，便用二维数组。虽然二维数组多用了些空间，但是代码很直观。

01背包，对一个物品的选择是，不放 or 放。

完全背包，对一个物品的选择是，不放 or 放一个 or 放两个… 仅此而已。所以在掌握01背包之后，完全背包很容易实现。

本题略微有点难度的地方是，当背包容量为0时，需要初始化为1，表示仅使用某种硬币，可以完全找零。(自行调试，体会)

#include <vector>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            // 思路：完全背包问题
            // 无法放下；可以放下：不放，放1一个，两个，....
    
            int kinds = coins.size();
    
            // dp[i][j]表示，前i种硬币，凑凑恰好为j，的组合数
            // 整体初始化为零，默认全部找不开
            // 初始化第一列，当需要找0元。表示使用某一种硬币可以全部找开。
            // 初始化第一行，使用第一种硬币，凑amount；如果可以凑上，初始化为1
            vector<vector<int>> dp(kinds,vector<int>(amount+1,0));
            for(int i=0; i<kinds; i++)
                dp[i][0] = 1;
            for(int i=1; i<=amount; i++){
                if(i%coins[0]==0)
                    dp[0][i] = 1;
            }
    
            for(int i=1; i<kinds; i++){ // 遍历物品
                for(int j=1; j<=amount; j++){ // 遍历背包
                    if(coins[i] > j)
                        dp[i][j] = dp[i-1][j]; // 当前物品无法放入，相当于使用前i-1种物品，恰好放入j容量
                    else{
                        // 可以放入:选择不放，放入一个，放入两个....
                        int cnt = j/coins[i];
                        int max_method = dp[i-1][j];
                        for(int k=1; k<=cnt; k++){
                            max_method += dp[i-1][j-k*coins[i]];
                        }
                        dp[i][j] = max_method;
                    }
                    
                }
            }
    
            // for(auto vec:dp){
            //     for(auto v : vec)
            //         cout<<v<<" ";
            //     cout<<endl;
            // }
    
            return dp[kinds-1][amount];
        }
    };
    
    int main(void){
        // vector<int> coins = {200,217,234,251,268,285,302,319,336,353,370,387,404,421,438,455,472,489,506,523,540,557,574,591,608,625,642,659,676,693,710,727,744,761,778,795,812,829,846,863,880,897,914,931,948,965,982,999,1016,1033,1050,1067,1084,1101,1118,1135,1152,1169,1186,1203,1220,1237,1254,1271,1288,1305,1322,1339,1356,1373,1390,1407,1424,1441,1458,1475,1492,1509,1526,1543,1560,1577,1594,1611,1628,1645,1662,1679,1696,1713,1730,1747,1764,1781,1798,1815,1832,1849,1866,1883,1900,1917,1934,1951,1968,1985,2002,2019,2036,2053,2070,2087,2104,2121,2138,2155,2172,2189,2206,2223,2240,2257,2274,2291,2308,2325,2342,2359,2376,2393,2410,2427,2444,2461,2478,2495,2512,2529,2546,2563,2580,2597,2614,2631,2648,2665,2682,2699,2716,2733,2750,2767,2784,2801,2818,2835,2852,2869,2886,2903,2920,2937,2954,2971,2988,3005,3022,3039,3056,3073,3090,3107,3124,3141,3158,3175,3192,3209,3226,3243,3260,3277,3294,3311,3328,3345,3362,3379,3396,3413,3430,3447,3464,3481,3498,3515,3532,3549,3566,3583,3600,3617,3634,3651,3668,3685,3702,3719,3736,3753,3770,3787,3804,3821,3838,3855,3872,3889,3906,3923,3940,3957,3974,3991,4008,4025,4042,4059,4076,4093,4110,4127,4144,4161,4178,4195,4212,4229,4246,4263,4280,4297,4314,4331,4348,4365,4382,4399,4416,4433,4450,4467,4484,4501,4518,4535,4552,4569,4586,4603,4620,4637,4654,4671,4688,4705,4722,4739,4756,4773,4790,4807,4824,4841,4858,4875,4892,4909,4926,4943,4960,4977,4994};
        // int amount = 4000;
    
        vector<int> coins = {1,2,5};
        int amount = 10;
        Solution s;
        cout<<s.change(amount,coins);
    }

[518. _ II]: https://leetcode-cn.com/problems/coin-change-2/
[-]: https://blog.csdn.net/sinat_38816924/article/details/83045913
[II-]: https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode-soluti-f7uh/