dp第九天

139. 单词拆分

背包也是dp问题，这题直接跳过了01背包啥的，这个是完全背包，表示一个物品可以多次使用，同时要求返回的是是否可以满足，不需要返回排列组合。

https://leetcode-cn.com/problems/word-break/comments/，从这个题解，可以看出来一些东西，具体的就是卡尔所讲的dp五部曲，不过这里我还没太多实践。注意下subStrinng不包含有节点。

本周小结！（动态规划系列五） | 代码随想录 (programmercarl.com)

/**
 139. 单词拆分
 给你一个字符串 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


 提示：

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

 * @author zeroheart
 *
 */
public class Question139 {
    public static boolean wordBreak(String s, List<String> wordDict) {
        // https://leetcode-cn.com/problems/word-break/comments/
        // 排列的话，就是{1,3},{3,1}视为两种情况的，外层需要是背包，组合的话外层是物品，这里不需要知道排列组合，顺序没有要求

        // 背包问题，重复使用，是完全背包
        // dp[i]表示长度i的字符串，可以用单词拼出来的可能，dp[i] = true;就是可以拼出来
        // 对于j，(j-i)之间的字符串为list中的单词，并且dp[j] = 1，那么dp[i] = 1;
        int length = s.length();
        int[] dp = new int[length+1];
        dp[0] = 1;

        for(int i = 1; i<=length; i++)// 背包
        {
            for(int j = 0; j<i; j++)// 物品
            {
                String substring = s.substring(j, i);
                System.out.println(substring);
                if(wordDict.contains(substring) && dp[j]==1){
                    dp[i] = 1;
                }
            }
        }

        return dp[s.length()] > 0;
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List wd = Arrays.asList(new String[]{"leet", "code"});
        System.out.println(wordBreak(s, wd));
    }
}

42. 接雨水

这一题，看题解其实不难，理解了就好，对于下标i，找到左边最大值，右边的最大值，取小的，作为桶边，超过边的记为0，小于边的差值就是雨水量。

/**
 42. 接雨水
 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。



 示例 1：



 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 输出：6
 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 示例 2：

 输入：height = [4,2,0,3,2,5]
 输出：9


 提示：

 n == height.length
 1 <= n <= 2 * 10^4
 0 <= height[i] <= 10^5

 * @author zeroheart
 *
 */
public class Question42 {
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length]; // i 左边的最大值
        int[] maxRight = new int[height.length];// i 右边的最大值

        for(int i=1; i<height.length; i++){
            maxLeft[i] = Math.max(maxLeft[i-1], height[i-1]); // 这里存在递推
        }

        for(int i=height.length-2; i>=0; i--){
            maxRight[i] = Math.max(maxRight[i+1], height[i+1]); // 这里存在递推
        }

        int sum = 0;
        for(int i=0; i<height.length; i++){
            int min = Math.min(maxLeft[i], maxRight[i]);
            sum += Math.max(0, min - height[i]);
        }
        return sum;
    }

    public static void main(String[] args) {
    }
}