代码随想录第三十八天

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

思路：

这道题是很明显的完全背包问题，但是我们要注意，它加了一个如果没有任何一种硬币组合能组成总金额，返回-1，最开始我想的是设置初始变量为0，但是dp[amount]的最终答案可能为0，所以我选择取INT_MAX-1,如果取不到的话我们的dp[amount]就是原来的INT_MAX这个值，返回-1，最后的操作就跟之前的一样，很快就能得到最终答案。

解答：

int coinChange(int* coins, int coinsSize, int amount) {
    int* dp = malloc(sizeof(int)*(amount+1));
    for(int i = 0;i < amount+1;i++)
    {
        dp[i] = INT_MAX-1;
    }
    dp[0] = 0;
    for(int i = 0;i < coinsSize;i++)
    {
        for(int j = coins[i];j <= amount;j++)
        {
            if(amount-coins[i]>= 0)
            dp[j] = fmin(dp[j],dp[j-coins[i]]+1);
        }
    }
    if(dp[amount] == INT_MAX-1)
    {
        return -1;
    }
    return dp[amount];
}

279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

思路：

使用动态规划解决。构造一个数组 dp，其中 dp[j] 表示组成数字 j 所需的最少完全平方数个数。首先计算所有小于等于 n 的完全平方数存入 nums。初始化 dp 数组，dp[0] = 0 表示 0 无需任何平方数，其余值初始化为较大的数。然后遍历每个平方数 nums[i]，对每个数字 j（从 nums[i] 到 n），尝试用当前平方数更新 dp[j] 的最优值，状态转移方程为 dp[j] = min(dp[j], dp[j - nums[i]] + 1)。最终 dp[n] 即为目标结果，表示组成 n 的最少完全平方数个数。

解答：

int numSquares(int n) {
    int x = 1;
    int maxIndex = 0;
    while (x * x <= n) {
        maxIndex++;
        x++;
    }
    int* nums = malloc(sizeof(int) * maxIndex);
    for (int i = 0; i < maxIndex; i++) {
        nums[i] = (i + 1) * (i + 1);
    }
    int* dp = malloc(sizeof(int)*(n+1));
    for(int i = 0; i <= n;i++)
    {
        dp[i] = INT_MAX-1;
    }
    dp[0] = 0;
    for(int i = 0;i < maxIndex;i++)
    {
        for(int j = nums[i];j <= n;j++)
        {
            if(j - nums[i] >= 0)
            dp[j] = fmin(dp[j],dp[j-nums[i]]+1);
        }
    }
    return dp[n];
}

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

思路：

我们可以利用一个布尔数组 dp 表示字符串的前缀是否能被字典单词组合成。初始化 dp[0] = true（空字符串可拆分），然后遍历字符串 s 的每个位置 i，对每个字典单词检查：若当前单词能与 s[i-wordLen:i] 匹配且之前的部分 dp[i-wordLen] 可拆分，则更新 dp[i] = true。最终返回 dp[len] 表示字符串是否可由字典单词完全构造。这里要注意strcnmp的使用。

解答：

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int len = strlen(s); 
    bool dp[len+1];
    memset(dp,false,sizeof(dp));
    dp[0] = true;
    for(int i = 1;i <= len;i++)
    {
        for(int j = 0;j < wordDictSize;j++)
        {
            int word = strlen(wordDict[j]);
            int k = i - word;
            if(k < 0)
            {
                continue;
            }
            dp[i] = (dp[k] && !strncmp(s+k,wordDict[j],word)) || dp[i];
        }
    }
    return dp[len];
}

56.携带矿石资源

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

输入描述

输入共包括四行，第一行包含两个整数 C 和 N，分别表示宇航舱的容量和矿石的种类数量。

接下来的三行，每行包含 N 个正整数。具体如下：

第二行包含 N 个整数，表示 N 种矿石的重量。

第三行包含 N 个整数，表示 N 种矿石的价格。

第四行包含 N 个整数，表示 N 种矿石的可用数量上限。

输出描述

输出一个整数，代表获取的最大价值。

输入示例

10 3
1 3 4
15 20 30
2 3 2

输出示例

90

提示信息

数据范围：
1 <= C <= 2000;
1 <= N <= 100;
1 <= w[i], v[i], k[i] <= 1000;

思路：

这里是一个多重背包问题，也就是一个01背包问题，这里要从大到小进行排序，但是这里要注意，我们需要使用一个三重循环，因为它的个数和价值都是由我们自己决定，所以需要在加上一重循环，满足次数没有超过规定次数，同时没有超出背包容量，最后也就得到答案了。

解答：

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int c,n;
    scanf("%d %d",&c,&n);
    int weight[n+1];
    int value[n+1];
    int number[n+1];
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&weight[i]);
    }
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&value[i]);
    }
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&number[i]);
    }
    int* dp = calloc(c+1,sizeof(int));
    for(int i = 0;i < n;i++)
    {
        for(int j = c;j >= weight[i];j--)
        {
            for(int k = 1;k <= number[i] && (j-k*weight[i])>=0;k++)
            {
                dp[j] = fmax(dp[j],dp[j-k*weight[i]]+value[i]*k);
            }
        }
    }
    printf("%d",dp[c]);
}

反思

今天的题目都还好，我觉得动态规划也需要做一些题目来培养相应的题感，但是还是需要深入思考，这只是第一次接触，还需要对其进行相应的练习。