动态规划Day08(背包结束，未写完)-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划Day08(背包结束，未写完)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

139.单词拆分(需要重新写)

力扣题目链接(opens new window)

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 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

看到题目的第一想法

使用背包，但是不知道这些字符串要怎么处理比较好

看到代码随想录之后的想法

这是求排列数，判断[i，j] 是否有匹配的字符串，有则为true

while的条件

代码随想录中的实现是 while(i>=len&&dp[i-len]==true&&word.equals(s.subString(i-len,i)))

自己实现过程中遇到的困难

dp[i]代表当前位置是否可以用word来表示

while的条件

代码随想录中的实现是 while(i>=len&&dp[i-len]==true&&word.equals(s.subString(i-len,i)))

dp[0]对应空串，其他的都是一一对应

要注意 boonlean数组的定义为new boolean[s.length()+1] 我定义成s.length()了

同时遍历字符串时，i<=s.length 我写的时候没有加=号

return 也是dp[s.length()]

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //dp数组的定义和下标的含义
        //若当前位置能被wordic种的字典拼出则为true ，否则为false
        //确定递推公式
        // if([i,j]是wordDict，且i 为true)
        // 则dp[j]=true
        //dp数组初始化
        //dp[0] = true
        //确定遍历顺序
        //求的排列数，要先背包后物品
        //从前往后，一个单词可以重复出现，完全背包
        //举例推导dp数组
        //s.length()+1
        //dp[0]代表空串一定为true
        //dp[i] 代表0~i是否能用字典表示
        boolean[] dp = new boolean[s.length()+1]; 
        
        for(int i=0;i<dp.length;i++){
            dp[i]=false;
        }
        dp[0] = true;
        /*for(int i=0;i<s.length();i++){
            for(String word:wordDict){
                int len = word.length();
                int j = i+len;
                //这里应该是j-i,j
                if(dp[i]==true&&word.equals(s.substring(j-i,j))){
                    dp[j]=true;
                }
            }
        }*/
        //这里是<=
        for(int i=1;i<=s.length();i++){
            for(String word:wordDict){
                int len = word.length();
                //这里应该是i-len,i
                if(i>=len&&dp[i-len]==true&&word.equals(s.substring(i-len,i))){
                    dp[i]=true;
                }
            }
        }
        //应该是length+1
        return dp[s.length()];

    }
}

背包问题总结

动态规划Day08(背包结束，未写完),动态规划,算法

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

动态规划：416.分割等和子集(opens new window)
动态规划：1049.最后一块石头的重量 II(opens new window)

最多装多少，or是否能装满，是求在目标背包容量能容纳的最大的value，则需要去根据当前的物品来进行比较Math.max(dp[j],dp[j-weight[i]]+value[i]);

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

动态规划：494.目标和(opens new window)
动态规划：518. 零钱兑换 II(opens new window)
动态规划：377.组合总和Ⅳ(opens new window)
动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

装满背包有多少种方法？则需要累计能装满背包的方法的个数，若当前为nums[i]，则dp[j]+=dp[j-nums[i]]，凑成j需要去找dp[j-nums[i]]有多少个

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

动态规划：474.一和零(opens new window)

这道题涉及到了二维数组，背包是二维的，[m，n] dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

动态规划：322.零钱兑换(opens new window)
动态规划：279.完全平方数

求的是和之前比的最小值 dp[j] = Math.min(dp[j],dp[j-nums[i]]+1);

遍历顺序

01背包

在动态规划：关于01背包问题，你该了解这些！ (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

和动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中，我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，大家需要注意！

#完全背包

说完01背包，再看看完全背包。

在动态规划：关于完全背包，你该了解这些！ (opens new window)中，讲解了纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

动态规划Day08(背包结束，未写完)