秋招突击——7/1——复习{}——新作{零钱兑换、单词拆分、最长递增子序列、乘积最大子数组}-CSDN博客

本文链接：https://blog.csdn.net/Blackoutdragon/article/details/140097185

文章目录

引言

今天的有点意外，女朋友的工卡丢了，找了一上午，忙了一上午，就简单听了听八股，到了中午才开始做这个算法。

复习

新作

零钱兑换

题目链接
在这里插入图片描述
重点

返回能够凑成总金额所需要的最少的硬币个数
如果不能凑成，就返回-1
每一种硬币都是无限的

个人实现

这就是一个完全背包问题，背包的容量是amount，然后物品种类是你所拥有的硬币个数，然后每一个硬币都是无限的。
这是一个二维的数组，我可以先写出来，在使用公式和滚动数组进行优化。

class Solution {
   
public:
    int coinChange(vector<int>& coins, int amount) {
   
        int nc = coins.size();
        // 好奇的是这样写，是否会导致结果不同？会自动创建对应的子序列吗？
        vector<vector<int>> f(nc + 1);
        // 初始化f[0]保证结果相同
        for(int j = 0;j <= amount;j ++){
   
            f[0].push_back(INT_MAX);
            if()
        }
        for(int i = 1;i < nc ;i ++){
   
            // 添加一个新的元素
            for(int j = 0;j <= amount;j ++){
   
                f[i].push_back(INT_MAX);
                for(int k = 0; k * coins[i] <= j;k ++){
   
                    // 每一个物体放n次
                    // 判定一下，是否越界了
                    f[i][j] = min(f[i][j],f[i - 1][j - k * coins[i]] + k);
                }
            }
        }

        // 判定目标是否是否可以进行组装
        if(f[nc - 1][amount])  return -1;
        else return f[nc - 1][amount];

    }
};

在这里插入图片描述
难点

真的难受，又卡住了，卡在了怎么对数组的元素进行初始化，之前这个问题就做过了，如今还是这个问题，真的难受。
等下重点，好好看看！

初始化二维矩阵的方式

  // 声明并初始化一个二维矩阵，大小为 rows x cols，所有元素初始值为 initial_value
    std::vector<std::vector<int>> matrix(rows, std::vector<int>(cols, initial_value));

修改之后的操作

class Solution {
   
public:
    int coinChange(vector<int>& coins, int amount) {
   
        int nc = coins.size();
        // 好奇的是这样写，是否会导致结果不同？会自动创建对应的子序列吗？
        vector<vector<int>> f(nc + 1,vector<int>(amount + 1,1e7));
        // 初始化f[0]保证结果相同
        f[0][0] = 0;
        
        // 构建一个新的数组，保证不越界
        vector<int> t;
        t.push_back(0);
        t.insert(t.end(),coins.begin(),coins.end());

        // 遍历生成对应的数组
        for(int i = 1;i <= nc ;i ++){
   
            // 添加一个新的元素
            for(int j = 0;j <= amount;j ++){
   
                for(int k =