判断题 偏易
#20239

下面代码采用动态规划求解零钱兑换问题:给定 n 种硬币,第 i 种硬币的面值为 coins[i - 1] ,目标金额为 amt ,每种硬币可以重复选取,求能够凑…

下面代码采用动态规划求解零钱兑换问题:给定 n 种硬币,第 i 种硬币的面值为 coins[i - 1] ,目标金额为 amt ,每种硬币可以重复选取,求能够凑出目标金额的最少硬币数量;如果不能凑出目标金额,返回 -1 。( )

int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a)
                dp[a] = dp[a];
            else
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:对
这道题暂未补解析。