时间戳

首页 > 解决方案 > 如何在硬币找零中添加记忆

c++ - 如何在硬币找零中添加记忆

问题描述

我正在研究硬币找零的 Leetcode问题。我想出了一个蛮力解决方案，并对如何添加记忆有一些想法，但看起来我错过了一些东西。下面是我的非记忆功能。

我最初在考虑创建一个哈希图，它存储向量、索引和总和的元组，并针对它存储相应的总和值，我在基本情况下使用它。但是空运行它，它看起来不正确。

非常感谢任何提示/帮助。

void minCoins_Helper2(std::vector<int> coins, int sum, int index, int currCoins, int &min){
    // Base cases
    if(index == coins.size())
        return;
    if(sum < 0)
        return;
    if(sum == 0){
        if(currCoins < min)
            min = currCoins;
        return;
    }
    // Include the coin
    minCoins_Helper2(coins, sum - coins[index], index, currCoins+1, min);
    // Exclude the coin
    minCoins_Helper2(coins, sum, index+1, currCoins, min);
}

int minCoins2(std::vector<int> coins, int sum){
    int min = INT_MAX;
    minCoins_Helper2(coins, sum, 0, 0, min);;
    return min;
}

标签： c++dynamic-programming

解决方案

您不需要存储硬币矢量。

在这个问题中，你只需要一个二维数组，比如你的总和是dp[i][j]哪里，你的索引是哪里。ij

在 结束时minCoins_helper2，在递归调用之后，您必须将 dp[sum][index] 存储为两个递归调用的最小答案。

然后在顶部，// include the coins您应该检查是否以前计算过 dp[sum][index] ，然后不要递归调用它以节省时间。

推荐阅读