一文刷题学懂(一维动态规划)——java+python——3/5

这篇具有很好参考价值的文章主要介绍了一文刷题学懂(一维动态规划)——java+python——3/5。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

三、单词拆分

给你一个字符串 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.Java解答

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}




2.python解答

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        import functools
        @functools.lru_cache(None)
        def back_track(s):
            if(not s):
                return True
            res=False
            for i in range(1,len(s)+1):
                if(s[:i] in wordDict):
                    res=back_track(s[i:]) or res
            return res
        return back_track(s)



3.主要思想
动态规划思想文章来源地址https://www.toymoban.com/news/detail-842710.html

到了这里,关于一文刷题学懂(一维动态规划)——java+python——3/5的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划(一)一维DP

    通过上篇文章,动态规划(零)入门概念相信大家已经对动态规划有了一些概念上的理解,那么如何运用动态规划去解决问题呢,首先要知道动态规划的解题步骤。 动态规划的步骤如下: (1) 设计状态 (2) 写出状态转移方程 (3) 设定初始状态 (4) 执行状态转移 (5) 返回最终的解 下

    2024年02月07日
    浏览(39)
  • 动态规划—— 01背包问题(一维,二维)

    0-1背包问题是一个经典问题,特别是在算法和动态规划领域。问题是关于一个小偷,他有一个可以携带最大重量的背包,并且他有一组物品,其中每个物品都有自己的价值和重量。小偷希望在不超过背包所能承载的最大重量的情况下,最大化他从这些物品中获得的总价值。问

    2024年02月19日
    浏览(44)
  • class066 一维动态规划【算法】

    算法讲解066【必备】从递归入手一维动态规划 // 斐波那契数 // 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 // 该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。 // 也就是:F(0) = 0,F(1) = 1 // F(n) = F(n - 1) + F(n - 2),其中 n 1 // 给定 n ,请计算

    2024年02月04日
    浏览(34)
  • 一维动态规划经典力扣题目(一)

    目录 题一:斐波那契数列 题目二:最低票价 题三:解码方法 递归方法是2的n次方的时间复杂度。 递归代码: 带有缓存的递归,会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法:         代码:         代码:

    2024年02月21日
    浏览(41)
  • 【leetcode100-086到090】【动态规划】一维五题合集2

    【单词拆分】 给你一个字符串  s  和一个字符串列表  wordDict  作为字典。如果可以利用字典中出现的一个或多个单词拼接出  s  则返回  true 。 注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 思路: 首先,我们依次考虑s的前i个字母能否被

    2024年02月19日
    浏览(37)
  • 从二维数组到一维数组——探索01背包问题的动态规划优化

    本文将继续上一篇博客爬楼梯之后继续讲解同样用到了动态规划的 01背包问题 在解决动态规划问题时,我们经常面临着空间复杂度的挑战。01背包问题是一个典型的例子,通常使用二维数组来表示状态转移,但这样会带来额外的空间开销。在本文中,我们将探讨如何通过优化

    2024年04月11日
    浏览(58)
  • Leetcode动态规划篇(0-1背包问题一维和二维dp实现)

    🤗专栏:每日算法学习 💬个人主页:个人主页 🤓情况描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态,取或者不取。

    2023年04月09日
    浏览(42)
  • 【LeetCode动态规划#06】分割等和子集(01背包问题一维写法实战)

    分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割

    2023年04月09日
    浏览(65)
  • 【LeetCode动态规划#07】01背包问题一维写法(状态压缩)实战,其二(目标和、零一和)

    力扣题目链接(opens new window) 难度:中等 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例: 输入

    2023年04月18日
    浏览(62)
  • 《动态规划》刷题训练

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年01月19日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包