{"id":2611,"date":"2022-04-05T19:18:31","date_gmt":"2022-04-05T11:18:31","guid":{"rendered":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2611"},"modified":"2022-04-06T22:29:49","modified_gmt":"2022-04-06T14:29:49","slug":"dp%e7%ac%ac%e4%b9%9d%e5%a4%a9","status":"publish","type":"post","link":"https:\/\/www.zeroheart.xyz\/wordpress\/?p=2611","title":{"rendered":"dp\u7b2c\u4e5d\u5929"},"content":{"rendered":"\n

139. \u5355\u8bcd\u62c6\u5206<\/a><\/p>\n\n\n\n

\u80cc\u5305\u4e5f\u662fdp\u95ee\u9898\uff0c\u8fd9\u9898\u76f4\u63a5\u8df3\u8fc7\u4e8601\u80cc\u5305\u5565\u7684\uff0c\u8fd9\u4e2a\u662f\u5b8c\u5168\u80cc\u5305\uff0c\u8868\u793a\u4e00\u4e2a\u7269\u54c1\u53ef\u4ee5\u591a\u6b21\u4f7f\u7528\uff0c\u540c\u65f6\u8981\u6c42\u8fd4\u56de\u7684\u662f\u662f\u5426\u53ef\u4ee5\u6ee1\u8db3\uff0c\u4e0d\u9700\u8981\u8fd4\u56de\u6392\u5217\u7ec4\u5408\u3002<\/p>\n\n\n\n

https:\/\/leetcode-cn.com\/problems\/word-break\/comments\/<\/a>\uff0c\u4ece\u8fd9\u4e2a\u9898\u89e3\uff0c\u53ef\u4ee5\u770b\u51fa\u6765\u4e00\u4e9b\u4e1c\u897f\uff0c\u5177\u4f53\u7684\u5c31\u662f\u5361\u5c14\u6240\u8bb2\u7684dp\u4e94\u90e8\u66f2\uff0c\u4e0d\u8fc7\u8fd9\u91cc\u6211\u8fd8\u6ca1\u592a\u591a\u5b9e\u8df5\u3002\u6ce8\u610f\u4e0bsubStrinng\u4e0d\u5305\u542b\u6709\u8282\u70b9\u3002<\/p>\n\n\n\n

\u672c\u5468\u5c0f\u7ed3\uff01\uff08\u52a8\u6001\u89c4\u5212\u7cfb\u5217\u4e94\uff09 | \u4ee3\u7801\u968f\u60f3\u5f55 (programmercarl.com)<\/a><\/p>\n\n\n\n

\/**\n 139. \u5355\u8bcd\u62c6\u5206\n \u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s \u548c\u4e00\u4e2a\u5b57\u7b26\u4e32\u5217\u8868 wordDict \u4f5c\u4e3a\u5b57\u5178\u3002\u8bf7\u4f60\u5224\u65ad\u662f\u5426\u53ef\u4ee5\u5229\u7528\u5b57\u5178\u4e2d\u51fa\u73b0\u7684\u5355\u8bcd\u62fc\u63a5\u51fa s \u3002\n\n \u6ce8\u610f\uff1a\u4e0d\u8981\u6c42\u5b57\u5178\u4e2d\u51fa\u73b0\u7684\u5355\u8bcd\u5168\u90e8\u90fd\u4f7f\u7528\uff0c\u5e76\u4e14\u5b57\u5178\u4e2d\u7684\u5355\u8bcd\u53ef\u4ee5\u91cd\u590d\u4f7f\u7528\u3002\n\n\n\n \u793a\u4f8b 1\uff1a\n\n \u8f93\u5165: s = \"leetcode\", wordDict = [\"leet\", \"code\"]\n \u8f93\u51fa: true\n \u89e3\u91ca: \u8fd4\u56de true \u56e0\u4e3a \"leetcode\" \u53ef\u4ee5\u7531 \"leet\" \u548c \"code\" \u62fc\u63a5\u6210\u3002\n \u793a\u4f8b 2\uff1a\n\n \u8f93\u5165: s = \"applepenapple\", wordDict = [\"apple\", \"pen\"]\n \u8f93\u51fa: true\n \u89e3\u91ca: \u8fd4\u56de true \u56e0\u4e3a \"applepenapple\" \u53ef\u4ee5\u7531 \"apple\" \"pen\" \"apple\" \u62fc\u63a5\u6210\u3002\n \u6ce8\u610f\uff0c\u4f60\u53ef\u4ee5\u91cd\u590d\u4f7f\u7528\u5b57\u5178\u4e2d\u7684\u5355\u8bcd\u3002\n \u793a\u4f8b 3\uff1a\n\n \u8f93\u5165: s = \"catsandog\", wordDict = [\"cats\", \"dog\", \"sand\", \"and\", \"cat\"]\n \u8f93\u51fa: false\n\n\n \u63d0\u793a\uff1a\n\n 1 <= s.length <= 300\n 1 <= wordDict.length <= 1000\n 1 <= wordDict[i].length <= 20\n s \u548c wordDict[i] \u4ec5\u6709\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210\n wordDict \u4e2d\u7684\u6240\u6709\u5b57\u7b26\u4e32 \u4e92\u4e0d\u76f8\u540c\n\n * <\/em>@author <\/em><\/strong>zeroheart\n *\n *\/\n<\/em>public class Question139 {\n    public static boolean wordBreak(String s, List<String> wordDict) {\n        \/\/ https:\/\/leetcode-cn.com\/problems\/word-break\/comments\/\n        \/\/ \u6392\u5217\u7684\u8bdd\uff0c\u5c31\u662f{1,3},{3,1}\u89c6\u4e3a\u4e24\u79cd\u60c5\u51b5\u7684\uff0c\u5916\u5c42\u9700\u8981\u662f\u80cc\u5305\uff0c\u7ec4\u5408\u7684\u8bdd\u5916\u5c42\u662f\u7269\u54c1\uff0c\u8fd9\u91cc\u4e0d\u9700\u8981\u77e5\u9053\u6392\u5217\u7ec4\u5408\uff0c\u987a\u5e8f\u6ca1\u6709\u8981\u6c42\n\n        \/\/ \u80cc\u5305\u95ee\u9898\uff0c\u91cd\u590d\u4f7f\u7528\uff0c\u662f\u5b8c\u5168\u80cc\u5305\n        \/\/ dp[i]\u8868\u793a\u957f\u5ea6i\u7684\u5b57\u7b26\u4e32\uff0c\u53ef\u4ee5\u7528\u5355\u8bcd\u62fc\u51fa\u6765\u7684\u53ef\u80fd\uff0cdp[i] = true;\u5c31\u662f\u53ef\u4ee5\u62fc\u51fa\u6765\n        \/\/ \u5bf9\u4e8ej\uff0c(j-i)\u4e4b\u95f4\u7684\u5b57\u7b26\u4e32\u4e3alist\u4e2d\u7684\u5355\u8bcd\uff0c\u5e76\u4e14dp[j] = 1\uff0c\u90a3\u4e48dp[i] = 1;\n        int length = s.length();\n        int[] dp = new int[length+1];\n        dp[0] = 1;\n\n        for(int i = 1; i<=length; i++)\/\/ \u80cc\u5305\n        {\n            for(int j = 0; j<i; j++)\/\/ \u7269\u54c1\n            {\n                String substring = s.substring(j, i);\n                System.out<\/em>.println(substring);\n                if(wordDict.contains(substring) && dp[j]==1){\n                    dp[i] = 1;\n                }\n            }\n        }\n\n        return dp[s.length()] > 0;\n    }\n\n    public static void main(String[] args) {\n        String s = \"leetcode\";\n        List wd = Arrays.asList<\/em>(new String[]{\"leet\", \"code\"});\n        System.out<\/em>.println(wordBreak<\/em>(s, wd));\n    }\n}<\/pre>\n\n\n\n
42. \u63a5\u96e8\u6c34<\/a><\/p>\n\n\n\n
\u8fd9\u4e00\u9898\uff0c\u770b\u9898\u89e3\u5176\u5b9e\u4e0d\u96be\uff0c\u7406\u89e3\u4e86\u5c31\u597d\uff0c\u5bf9\u4e8e\u4e0b\u6807i\uff0c\u627e\u5230\u5de6\u8fb9\u6700\u5927\u503c\uff0c\u53f3\u8fb9\u7684\u6700\u5927\u503c\uff0c\u53d6\u5c0f\u7684\uff0c\u4f5c\u4e3a\u6876\u8fb9\uff0c\u8d85\u8fc7\u8fb9\u7684\u8bb0\u4e3a0\uff0c\u5c0f\u4e8e\u8fb9\u7684\u5dee\u503c\u5c31\u662f\u96e8\u6c34\u91cf\u3002<\/p>\n\n\n\n
\/**
<\/em> 42. \u63a5\u96e8\u6c34
<\/em> \u7ed9\u5b9a n \u4e2a\u975e\u8d1f\u6574\u6570\u8868\u793a\u6bcf\u4e2a\u5bbd\u5ea6\u4e3a 1 \u7684\u67f1\u5b50\u7684\u9ad8\u5ea6\u56fe\uff0c\u8ba1\u7b97\u6309\u6b64\u6392\u5217\u7684\u67f1\u5b50\uff0c\u4e0b\u96e8\u4e4b\u540e\u80fd\u63a5\u591a\u5c11\u96e8\u6c34\u3002
<\/em>
<\/em>
<\/em>
<\/em> \u793a\u4f8b 1\uff1a
<\/em>
<\/em>
<\/em>
<\/em> \u8f93\u5165\uff1aheight = [0,1,0,2,1,0,1,3,2,1,2,1]
<\/em> \u8f93\u51fa\uff1a6
<\/em> \u89e3\u91ca\uff1a\u4e0a\u9762\u662f\u7531\u6570\u7ec4 [0,1,0,2,1,0,1,3,2,1,2,1] \u8868\u793a\u7684\u9ad8\u5ea6\u56fe\uff0c\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u63a5 6 \u4e2a\u5355\u4f4d\u7684\u96e8\u6c34\uff08\u84dd\u8272\u90e8\u5206\u8868\u793a\u96e8\u6c34\uff09\u3002
<\/em> \u793a\u4f8b 2\uff1a
<\/em>
<\/em> \u8f93\u5165\uff1aheight = [4,2,0,3,2,5]
<\/em> \u8f93\u51fa\uff1a9
<\/em>
<\/em>
<\/em> \u63d0\u793a\uff1a
<\/em>
<\/em> n == height.length
<\/em> 1 <= n <= 2 * 10^4
<\/em> 0 <= height[i] <= 10^5
<\/em>
<\/em> * <\/em>@author <\/em><\/strong>zeroheart
<\/em> *
<\/em> *\/
<\/em>public class Question42 {
    public int trap(int[] height) {
        int[] maxLeft = new int[height.length]; \/\/ i \u5de6\u8fb9\u7684\u6700\u5927\u503c
        int[] maxRight = new int[height.length];\/\/ i \u53f3\u8fb9\u7684\u6700\u5927\u503c

        for(int i=1; i<height.length; i++){
            maxLeft[i] = Math.max<\/em>(maxLeft[i-1], height[i-1]); \/\/ \u8fd9\u91cc\u5b58\u5728\u9012\u63a8
        }

        for(int i=height.length-2; i>=0; i--){
            maxRight[i] = Math.max<\/em>(maxRight[i+1], height[i+1]); \/\/ \u8fd9\u91cc\u5b58\u5728\u9012\u63a8
        }

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

    public static void main(String[] args) {
    }
}<\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
139. \u5355\u8bcd\u62c6\u5206 \u80cc\u5305\u4e5f\u662fdp\u95ee\u9898\uff0c\u8fd9\u9898\u76f4\u63a5\u8df3\u8fc7\u4e8601\u80cc\u5305\u5565\u7684\uff0c\u8fd9\u4e2a\u662f\u5b8c\u5168\u80cc\u5305\uff0c\u8868\u793a\u4e00\u4e2a\u7269\u54c1\u53ef\u4ee5\u591a\u6b21\u4f7f\u7528\uff0c\u540c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[155],"tags":[158,174,175],"_links":{"self":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2611"}],"collection":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2611"}],"version-history":[{"count":11,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2611\/revisions"}],"predecessor-version":[{"id":2622,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/2611\/revisions\/2622"}],"wp:attachment":[{"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zeroheart.xyz\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}