当前位置: 首页 > article >正文

<代码随想录> 算法训练营-2024.12.20

322. 零钱兑换
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[i][j]表示 提供到coins[i]的硬币,总金额为j的最少硬币个数 硬币个数无限,完全背包
        # 有两种取值,一种是取dp[i-1][j] 另一种是如果j比当前面额小,则可以取dp[m][n-coins[m]]+1
        size = len(coins)
        dp = [[10**4 + 1] * (amount + 1) for _ in range(size)]

        for i in range(size):
            dp[i][0] = 0

        for m in range(size):
            for n in range(1, amount + 1):
                if coins[m] <= n:
                    dp[m][n] = min(dp[m - 1][n], dp[m][n - coins[m]] + 1)
                else:
                    dp[m][n] = dp[m - 1][n]

        return -1 if dp[-1][-1] == 10**4 + 1 else dp[-1][-1]

279. 完全平方数
class Solution:
    def numSquares(self, n: int) -> int:
        #预处理完全平方数数组
        # 题目变成,完全背包中达到目标值的最少元素个数
        nums = []
        temp = 1
        while temp**2 <= n:
            nums.append(temp**2)
            temp += 1
        if nums[-1] == n:
            return 1

        size = len(nums)
        dp = [[10**4 + 1] * (n + 1) for _ in range(size)]

        for i in range(size):
            dp[i][0] = 0

        for i in range(size):
            for j in range(1, n + 1):
                if nums[i] <= j:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - nums[i]] + 1)
                else:
                    dp[i][j] = dp[i - 1][j]

        return -1 if dp[-1][-1] == 10**4 + 1 else dp[-1][-1]

139. 单词拆分
class Solution(object):
    def wordBreak(self, s, wordDict):

        # 先对单词按长度排序
        wordDict.sort(key=lambda x: len(x))
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        # 遍历背包
        for i in range(1, n + 1):
            # 遍历单词
            for word in wordDict:
                # 简单的 “剪枝”
                if len(word) > i:
                    break
                dp[i] = dp[i] or (dp[i - len(word)] and s[i - len(word): i] == word)
        return dp[-1]

http://www.kler.cn/a/448866.html

相关文章:

  • SQL,生成指定时间间隔内的事件次序号
  • Halcon例程代码解读:安全环检测(附源码|图像下载链接)
  • 网络安全概论——身份认证
  • 【游戏设计原理】22 - 石头剪刀布
  • (通信)海洋波导(Ocean Acoustic Waveguide)
  • Android -- 双屏异显之方法二
  • RAG基础知识及综述学习
  • 22 go语言(golang) - gin框架安装及使用(三)
  • Chrome 132 版本开发者工具(DevTools)更新内容
  • 【Redis】Redis RDB和AOF持久化介绍
  • go中常用的处理json的库
  • c++的类中的私有成员变量是否可以在cpp文件中再定义一次
  • Redis篇--常见问题篇2--缓存雪崩(过期时间分散,缓存预热,多级缓存)
  • Docker基础命令实战
  • whisper实时语音转文字
  • Java中使用四叶天动态代理IP构建ip代理池,实现httpClient和Jsoup代理ip爬虫
  • 梳理你的思路(从OOP到架构设计)_设计模式Template Method模式
  • Vue(二)
  • MATLAB绘图基础12:地理信息可视化
  • 1222面经
  • 【Go】Go数据类型详解—指针
  • LeetCode 26. 删除有序数组中的重复项 (C++实现)
  • 工具环境 | 工具准备
  • SSM 架构 Vue 赋能:WEB 开放性实验室智能管理系统
  • harmony UI组件学习(1)
  • 实验13 C语言连接和操作MySQL数据库