动态规划-完全背包问题——322.零钱兑换

1.题目解析

题目来源

322.零钱兑换——力扣

测试用例 

2.算法原理

1.状态表示

这里需要寻找硬币使总面值等于一个值求出所需硬币的最小个数，所以不妨设置一个二维dp表，即dp[i][j]：在[1,i]个硬币中选择的硬币总面值完全等于j时所需要的最小硬币个数

2.状态转移方程

3.初始化

4.填表顺序

从上到下，每一行从左到右

5.返回值 

判断最后一个位置是否可以选取，可以则返回其真实值，不可以则代表不能找出完全等于amount的最小硬币个数，返回-1

3.实战代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int coinChange(vector<int>& coins, int amount) 
    {
        int n = coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1));
        for(int j = 1;j <= amount;j++)
        {
            dp[0][j] = INF;
        }    

        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j <= amount;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1])
                {
                    dp[i][j] = min(dp[i][j],dp[i][j-coins[i-1]] + 1);
                }
            }
        }
        return (dp[n][amount] >= INF ? -1 : dp[n][amount]);
    }
};

代码解析 

4.优化 

原文地址：https://blog.csdn.net/2301_80689220/article/details/143824233

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！