数据结构学习 Leetcode322 零钱兑换

2023-12-27 20:16:32

关键词:动态规划 完全背包 记忆化搜索

一个套路:

  • 01背包:空间优化之后dp【target+1】,遍历的时候要逆序遍历
  • 完全背包:空间优化之后dp【target+1】,遍历的时候要正序遍历

题目:

方法一:

动态规划 完全背包

思路:

就是一个完全背包问题。有无限个相同的硬币。目标就是amount。

状态:dp[j]判断在放第i种硬币时,凑成目标金额为j所需要的最少硬币个数。(进行了滚动数组进行空间优化,正序遍历)

转移方程: dp[j]=min(dp[j],dp[j-coins[i]]+1)

  • 如果选dp[j]:不加这个硬币。
  • 如果选dp[j-coins[i]]+1:加这一个硬币。

初始条件:因为是找最小值,所以dp初始值设置成一个比较大的值,我设了1e5。

边界条件:初始条件里面,dp[0]要特别设置出来,dp[0]=0。因为在目标为0元、什么硬币都不用的时候,所需要的最少硬币个数为0。

画了一个dp状态推理过程的表格。纵坐标是j,横坐标是i。实际上dp状态是一维的,长度为amount+1,coins维被空间优化了。

amount\coins0125
00
1100001
21000021
31000032
41000042
510000531
610000632
710000742
810000843
910000953
10100001052
11100001163

?复杂度计算:

  • 时间复杂度O(nm) n为amount m为coins.size()
  • 空间复杂度O(n)?n为amount

代码:

#include <vector>
#include <iostream>
class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        std::vector<int> dp(amount + 1,1e5);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); ++i)
        {
            for (int j = coins[i]; j <= amount; ++j)
            {
                dp[j] = std::min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        if (dp[amount] == 1e5) return -1;
        else return dp[amount];
    }
};

方法二:

动态规划 记忆化

思路:

记忆化:把之前算过的状态记下来,减少搜索。

?复杂度计算:

  • 时间复杂度O(nm) n为amount m为coins.size()
  • 空间复杂度O(n)?n为amount

?代码:

class Solution {
    std::vector<int>count;
    int dp(std::vector<int>& coins, int rem)
    {
        if (rem < 0)return-1;
        if (rem == 0)return 0;
        if (count[rem - 1] != 0)return count[rem - 1];
        int min = INT_MAX;
        for (const auto& coin : coins)
        {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < min)
            {
                min = res + 1;//为什么要加个1
            }
        }
        count[rem - 1] = min == INT_MAX ? -1 : min;
        return count[rem - 1];
    }
public:
    int coinChange(std::vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        count.resize(amount);
        return dp(coins, amount);
    }
};

题目二:

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

思路:

和上面唯一不同的是求的是凑成总金额的硬币组合数

其实是基本一样的思路,主要是改变转移方程。

状态:dp[j]判断在放第i种硬币时,凑成目标金额为j的硬币组合数。(进行了滚动数组进行空间优化,正序遍历)

转移方程: dp[j]=dp[j]+dp[j-coins[i]]

  • dp[j]:不加这个硬币,凑成j的组合数。
  • dp[j-coins[i]]:加这一个硬币,凑成j的组合数。

初始条件:因为是找总和,所以dp初始值设置成0。

边界条件:初始条件里面,dp[0]要特别设置出来,dp[0]=1。因为在凑0元的时候,有一个方法就是啥都不放。

画了一个dp状态推理过程的表格。纵坐标是j,横坐标是i。实际上dp状态是一维的,长度为amount+1,coins维被空间优化了。

amount\coins0125
01
101
2012
3012
4013
50134
60145
70146
80157
90158
1001610
1101611

?复杂度计算:

  • 时间复杂度O(nm) n为amount m为coins.size()
  • 空间复杂度O(n)?n为amount

代码:

#include <vector>
#include <iostream>
//和前面问题不一样:
//给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        std::vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); ++i)
        {
            for (int j = coins[i]; j <= amount; ++j)
            {
                dp[j] += dp[j - coins[i]];
            }
        }
       return dp[amount];
    }
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135247670
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。