{"id":908,"date":"2019-12-20T17:16:05","date_gmt":"2019-12-20T09:16:05","guid":{"rendered":"http:\/\/47.101.202.111\/?p=908"},"modified":"2023-04-07T16:09:11","modified_gmt":"2023-04-07T08:09:11","slug":"%e7%ae%97%e6%b3%95%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92-%e5%88%9d%e6%ad%a5","status":"publish","type":"post","link":"http:\/\/139.196.114.170\/?p=908","title":{"rendered":"\u6c42\u89e3\u95ee\u9898\u6700\u4f18\u65b9\u6848 – \u52a8\u6001\u89c4\u5212\u57fa\u7840"},"content":{"rendered":"

\u52a8\u6001\u89c4\u5212<\/h2>\n

\u56de\u6eaf\u7a77\u4e3e\u6240\u6709\u5206\u652f\uff0c\u4e3b\u8981\u7528\u4e8e\u7f57\u5217\u51fa\u6240\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u5177\u4f53\u65b9\u6848\uff1b\u800c\u52a8\u6001\u89c4\u5212\u662f\u5728\u56de\u6eaf\u7684\u57fa\u7840\u4e0a\uff0c\u6bcf\u4e00\u9636\u6bb5\u7684\u51b3\u7b56\u4e2d\u9009\u62e9\u6700\u4f18\u7684\u4e00\u4e2a\uff0c\u4e3b\u8981\u7528\u4e8e\u7ed9\u51fa\u786e\u5b9a\u7684\u4e00\u4e2a\u6700\u4f18\u89e3\uff0c\u5373\u52a8\u6001\u89c4\u5212\u7528\u4e8e\u6c42\u89e3 \u53ef\u9009\u5143\u7d20\u5728\u4e00\u5b9a\u6761\u4ef6\u4e0b\u7684\u6700\u4f18\u65b9\u6848<\/strong> \u95ee\u9898\u3002\u5176\u5177\u4f53\u6b65\u9aa4\u662f\u8868\u793a\u95ee\u9898\u3001\u627e\u5230\u95ee\u9898\u4e4b\u95f4\u7684\u9012\u63a8\u5173\u7cfb\u3001\u786e\u5b9a\u9012\u63a8\u8fb9\u754c\u3001\u6839\u636e\u9012\u63a8\u65b9\u5411\u786e\u5b9a\u5143\u7d20\u8ba1\u7b97\u987a\u5e8f\u3001\u6839\u636e\u5143\u7d20\u8ba1\u7b97\u987a\u5e8f\u590d\u7528\u5b58\u50a8\u7a7a\u95f4\u51cf\u5c11\u6d88\u8017\u3002<\/p>\n

\u4ee50-1\u80cc\u5305\u95ee\u9898\u4e3a\u4f8b\u8bb2\u660e\u56de\u6eaf\u5230\u52a8\u6001\u89c4\u5212\u7684\u6f14\u53d8\u548c\u6539\u8fdb\uff0c\u5148\u7528\u56de\u6eaf\u5b9e\u73b0<\/p>\n

public static void main(String[] args) {\n    int value = backtracking(n - 1, capacity);\n}\n\npublic static int backtracking(int i, int c) {\n    if(i == -1) return 0;\n    if(c < w[i]) return dfs(i - 1, c);\n    return Math.max(backtracking(i - 1, c - w[i]) + v[i], backtracking(i - 1, c));\n}<\/code><\/pre>\n
\u6211\u4eec\u6ce8\u610f\u5230\u56de\u6eaf\u8ba1\u7b97\u4e86\u5927\u91cf\u7684\u91cd\u590d\u5b50\u95ee\u9898\uff0c\u4e00\u4e2a\u6734\u7d20\u7684\u60f3\u6cd5\u662f\u5c06\u5df2\u8ba1\u7b97\u8fc7\u7684\u7ed3\u679c\u5b58\u50a8\u91cd\u590d\u5229\u7528\uff0c\u6211\u4eec\u79f0\u4e3a\u8bb0\u5fc6\u5316\u641c\u7d22\u3002<\/p>\n
\u80fd\u5426\u8fdb\u4e00\u6b65\u4f18\u5316\u5462\uff1f\u6211\u4eec\u6ce8\u610f\u5230\u5b50\u95ee\u9898\u7684\u8ba1\u7b97\u987a\u5e8f\u540e\uff0c\u53ef\u4ee5\u6309\u7167\u62d3\u6251\u5c06\u6bcf\u79cd\u72b6\u6001\u53ea\u8ba1\u7b97\u4e00\u6b21\uff0c\u540e\u7eed\u6240\u6709\u72b6\u6001\u5747\u9700\u57fa\u4e8e\u5df2\u8ba1\u7b97\u72b6\u6001\u63a8\u5bfc\uff0c\u7528\u8fed\u4ee3\u6539\u5199\u8fdb\u4e00\u6b65\u51cf\u5c11\u9012\u5f52\u8c03\u7528\u7684\u6d88\u8017<\/p>\n
public int (int n, int capacity) {\n    int dp[n + 1][capacity + 1];\n\n    for(int i = 1; i <= n; i++)\n        for(int c = 1; c <= capacity; c++)\n            if(c >= w[i]) dp[i][c] = max(dp[i - 1][c - w[i]] + v[i], dp[i - 1][c]);\n            else dp[i][c] = dp[i - 1][c];\n\n    return dp[n][capacity];\n}<\/code><\/pre>\n
\u5728\u4e8c\u7ef4\u6570\u7ec4\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u901a\u8fc7\u5012\u63a8\u8bb0\u5f55\u65b9\u6848<\/p>\n
int c = capacity;\nfor(int i = n; i >= 1; i--) {\n    if(dp[i][c] != dp[i - 1][c]) {\n        System.out.printf("%d \u88ab\u9009\u62e9\\n", i);\n        i--;\n        c -= w[i];\n    }\n}<\/code><\/pre>\n
\u8fd8\u80fd\u4f18\u5316\u5417\uff1f\u6211\u4eec\u6ce8\u610f\u5230\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u8f6c\u79fb\u65b9\u5411\u5355\u4e00\uff0c\u4e14\u4e0e\u884c\u6216\u5217\u5e73\u884c\uff0c\u53ef \u4ec5\u7528\u4e00\u884c\u6216\u4e00\u5217\u6570\u636e\u8fed\u4ee3<\/strong> \u4ee5\u51cf\u5c11\u7a7a\u95f4\u4f7f\u7528\uff0c\u6ce8\u610f\u9632\u6b62\u8ba1\u7b97\u8fc7\u7a0b\u4e2d\u5b50\u95ee\u9898\u88ab\u8986\u76d6\uff0c\u56e0\u800c\u8981\u8003\u8651\u72b6\u6001\u8ba1\u7b97\u987a\u5e8f\u6b63\u5e8f\u3001\u9006\u5e8f\u3002\u6b64\u60c5\u51b5\u4e0b\u4e0d\u80fd\u518d\u5012\u63a8\u8bb0\u5f55\u65b9\u6848<\/p>\n
public int (int n, int capacity) {\n    int n = w.size();\n    int dp[capacity + 1];\n\n    for(int i = 1; i <= n; i++)\n        for(int c = capacity; c >= w[i]; c--)\n            dp[c] = max(dp[c - w[i]] + v[i], dp[c]);\n\n    return dp[capacity];\n}<\/code><\/pre>\n
\u5e94\u7528\u6848\u4f8b<\/h2>\n
\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/h4>\n
int LIS(vector<int> x)\n{\n    int dp[x.size()];\n    memset(dp, 0, sizeof(dp));\n    dp[0] = 1;\n    int ans = 1;\n\n    for (int i = 1; i < x.size(); i++)\n    {\n        int maxj = 0;\n        for (int j = 0; j < i; j++)\n            if (x[i] > x[j])\n                maxj = max(maxj, dp[j]);\n\n        dp[i] = maxj + 1;\n        ans = max(ans, dp[i]);\n    }\n\n    return ans;\n}<\/code><\/pre>\n
\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217<\/h4>\n
    int LCS(string x, string y)\n    {\n        int dp[x.length() + 1][y.length() + 1];\n        memset(dp, 0, sizeof(dp));\n\n        for (int i = 1; i <= x.length(); i++)\n            for (int j = 1; j <= y.length(); j++)\n                if (x[i - 1] == y[j - 1])\n                    dp[i][j] = dp[i - 1][j - 1] + 1;\n                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);\n\n        return dp[x.length()][y.length()];\n    }<\/code><\/pre>\n
\u7f16\u8f91\u8ddd\u79bb<\/a><\/h4>\n
\u25a0 \u95ee\u9898\u5b9a\u4e49\uff1adp[i][j]\u8868\u793aA[1..i]B[1..j]\u7684\u7f16\u8f91\u8ddd\u79bb\n\u25a0 \u8f6c\u79fb\u65b9\u7a0b\uff1aA[i] = B[j], dp[i][j] = dp[i-1][j-1]\n           A[i] \u2260 B[j], dp[i][j] = dp[i-1][j] + 1\uff0cA[i-1]\u52a0\u4e00\u4e2a\u5b57\u7b26\n           A[i] \u2260 B[j], dp[i][j] = dp[i][j-1] + 1\uff0cB[j-1]\u52a0\u4e00\u4e2a\u5b57\u7b26\uff0c\u7b49\u6548\u4e8eA[i]\u5220\u4e00\u4e2a\u5b57\u7b26\n           A[i] \u2260 B[j], dp[i][j] = dp[i-1][j-1] + 1\uff0cA[i]\u66ff\u6362\u4e00\u4e2a\u5b57\u7b26\n\u25a0 \u8fb9\u754c\u6761\u4ef6\uff1a\u7a7a\u4e32\u5230A[1...i]\u7684\u7f16\u8f91\u8ddd\u79bb\u4e3ai<\/code><\/pre>\n
public int minDistance(String word1, String word2) {\n    int m = word1.length() + 1;\n    int n = word2.length() + 1;\n    int[][] dp = new int[m][n];\n\n    for (int i = 0; i < m; i++)\n        dp[i][0] = i;\n\n    for (int i = 1; i < n; i++)\n        dp[0][i] = i;\n\n    for (int i = 1; i < m; i++) {\n        for (int j = 1; j < n; j++) {\n            if (word1.charAt(i - 1) == word2.charAt(j - 1))\n                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) + 1);\n            else\n                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;\n        }\n    }\n\n    return dp[m - 1][n - 1];\n}<\/code><\/pre>\n
\u6700\u957f\u56de\u6587\u5b50\u5e8f\u5217<\/h4>\n
int LPS(string s) {\n    int n = s.size();\n    int dp[n][n];\n    memset(dp, 0, sizeof(dp));\n\n    for (int j = 0; j < n; j++) {\n        dp[j][j] = 1;\n        for (int i = j - 1; i >= 0; i--)\n        {\n            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;\n            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);\n        }\n    }\n\n    return dp[0][n - 1];\n}<\/code><\/pre>\n
\u6700\u957f\u56de\u6587\u5b50\u4e32<\/a><\/h4>\n
\n\u25a0 \u95ee\u9898\u5b9a\u4e49\n        dp[i][j]\u8868\u793as[i..j]\u662f\u5426\u662f\u56de\u6587\u5b50\u4e32\n\u25a0 \u72b6\u6001\u8f6c\u79fb\n        s[i] == s[j] dp[i][j] = dp[i+1][j-1];\n        s[i] != s[j] dp[i][j] = false;\n\u25a0 \u8fb9\u754c\u6761\u4ef6\n        i == j dp[i][i] = true; \u5355\u5b57\u7b26\u4e3a\u56de\u6587\u4e32\n        i > j  dp[i][j] = true; \u7a7a\u4e32\u4e3a\u56de\u6587\u4e32\n\u25a0 \u8f6c\u79fb\u65b9\u5411\n        \u4f9d\u8d56\u5de6\u4e0b\u89d2\u72b6\u6001\uff0c\u8ba1\u7b97\u65f6\u5e94\u4ece\u5de6\u81f3\u53f3\u7ad6\u5411\u904d\u5386\n\u25a0 \u6eda\u52a8\u4f18\u5316\n        \u53ef\u4f18\u5316\u4e3a\u4e3a\u4e00\u7ef4\u5217\u6570\u7ec4\u7684\u6eda\u52a8\n<\/pre>\n
class Solution {\n    public String longestPalindrome(String s) {\n        if (s == null || s.length() == 0) return "";\n\n        boolean[] dp = new boolean[s.length()];\n        int maxLen = 1, maxLeft = 0, maxRight = 0;\n\n        for (int i = 0; i < s.length(); i++)\n            dp[i] = true;\n\n        for (int j = 1; j < s.length(); j++) {\n            for (int i = 0; i < j; i++) {\n                if (s.charAt(i) == s.charAt(j)) {\n                    if (dp[i] = dp[i + 1]) {\n                        int curLen = j - i + 1;\n                        if (curLen > maxLen) {\n                            maxLen = curLen;\n                            maxLeft = i;\n                            maxRight = j;\n                        }\n                    }\n                } else dp[i] = false;\n            }\n        }\n\n        return s.substring(maxLeft, maxRight + 1);\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u52a8\u6001\u89c4\u5212 \u56de\u6eaf\u7a77\u4e3e\u6240\u6709\u5206\u652f\uff0c\u4e3b\u8981\u7528\u4e8e\u7f57\u5217\u51fa\u6240\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u5177\u4f53\u65b9\u6848\uff1b\u800c\u52a8\u6001\u89c4\u5212\u662f\u5728\u56de\u6eaf\u7684\u57fa\u7840\u4e0a\uff0c\u6bcf\u4e00\u9636\u6bb5\u7684\u51b3\u7b56\u4e2d … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201c\u6c42\u89e3\u95ee\u9898\u6700\u4f18\u65b9\u6848 – \u52a8\u6001\u89c4\u5212\u57fa\u7840\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[12],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/908"}],"collection":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=908"}],"version-history":[{"count":49,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/908\/revisions"}],"predecessor-version":[{"id":2741,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/908\/revisions\/2741"}],"wp:attachment":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=908"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}