{"id":1073,"date":"2022-05-16T09:46:18","date_gmt":"2022-05-16T01:46:18","guid":{"rendered":"https:\/\/sanlangcode.com\/?p=1073"},"modified":"2022-05-16T09:46:18","modified_gmt":"2022-05-16T01:46:18","slug":"%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%ef%bc%88dp%ef%bc%89%e7%ae%97%e6%b3%95java%e5%85%a8%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/sanlangcode.com\/index.php\/2022\/05\/16\/%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92%ef%bc%88dp%ef%bc%89%e7%ae%97%e6%b3%95java%e5%85%a8%e8%a7%a3\/","title":{"rendered":"\u52a8\u6001\u89c4\u5212\uff08DP\uff09\u7b97\u6cd5Java\u5168\u89e3"},"content":{"rendered":"\n

\u52a8\u6001\u89c4\u5212(dynamic programming)<\/strong>\u662f\u8fd0\u7b79\u5b66\u7684\u4e00\u4e2a\u5206\u652f\uff0c\u662f\u6c42\u89e3\u51b3\u7b56\u8fc7\u7a0b(decision process)\u6700\u4f18\u5316\u7684\u6570\u5b66\u65b9\u6cd5\u3002\u5728\u9762\u8bd5\u7b14\u8bd5\u4e2d\u52a8\u6001\u89c4\u5212\u4e5f\u662f\u7ecf\u5e38\u4f5c\u4e3a\u8003\u9898\u51fa\u73b0\uff0c\u5176\u4e2d\u8f83\u4e3a\u7b80\u5355\u7684DP\u9898\u76ee\u6211\u4eec\u5e94\u8be5\u6709\u767e\u5206\u4e4b\u767e\u7684\u628a\u63e1\u987a\u5229\u89e3\u51b3\u624d\u53ef\u4ee5\u3002<\/p>\n\n\n\n

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

\u52a8\u6001\u89c4\u5212\u5b9e\u9645\u4e0a\u662f\u4e00\u7c7b\u9898\u76ee\u7684\u603b\u79f0\uff0c\u5e76\u4e0d\u662f\u6307\u67d0\u4e2a\u56fa\u5b9a\u7684\u7b97\u6cd5\u3002\u52a8\u6001\u89c4\u5212\u7684\u610f\u4e49\u5c31\u662f\u901a\u8fc7\u91c7\u7528\u9012\u63a8\uff08\u6216\u8005\u5206\u800c\u6cbb\u4e4b\uff09<\/strong>\u7684\u7b56\u7565\uff0c\u901a\u8fc7\u89e3\u51b3\u5927\u95ee\u9898\u7684\u5b50\u95ee\u9898\u4ece\u800c\u89e3\u51b3\u6574\u4f53\u7684\u505a\u6cd5\u3002\u52a8\u6001\u89c4\u5212\u7684\u6838\u5fc3\u601d\u60f3<\/strong>\u662f\u5de7\u5999\u7684\u5c06\u95ee\u9898\u62c6\u5206\u6210\u591a\u4e2a\u5b50\u95ee\u9898\uff0c\u901a\u8fc7\u8ba1\u7b97\u5b50\u95ee\u9898\u800c\u5f97\u5230\u6574\u4f53\u95ee\u9898\u7684\u89e3\u3002\u800c\u5b50\u95ee\u9898\u53c8\u53ef\u4ee5\u62c6\u5206\u6210\u66f4\u591a\u7684\u5b50\u95ee\u9898\uff0c\u4ece\u800c\u7528\u7c7b\u4f3c\u9012\u63a8\u8fed\u4ee3\u7684\u65b9\u6cd5\u89e3\u51b3\u8981\u6c42\u7684\u95ee\u9898\u3002<\/p>\n\n\n\n

\u52a8\u6001\u89c4\u5212\u7684\u89e3\u9898\u6838\u5fc3<\/h2>\n\n\n\n
\n\n\n\n

\u52a8\u6001\u89c4\u5212\u7684\u89e3\u9898\u6838\u5fc3\u4e3b\u8981\u5206\u4e3a\u4e24\u6b65\uff1a<\/p>\n\n\n\n

  1. \u7b2c\u4e00\u6b65\uff1a\u72b6\u6001\u7684\u5b9a\u4e49<\/strong><\/li>
  2. \u7b2c\u4e8c\u6b65\uff1a\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u5b9a\u4e49<\/strong><\/li><\/ol>\n\n\n\n

    \u5728\u8fd9\u91cc\uff0c\u6211\u4eec\u4e3a\u4e86\u907f\u514d\u6df7\u6dc6\u7528\u201c\u72b6\u6001\u201d\u8fd9\u4e2a\u8bcd\u6765\u66ff\u4ee3\u201c\u95ee\u9898\u201d\u8fd9\u4e2a\u8bcd\u3002\u201c\u95ee\u9898\u201d\u8868\u793a\u7684\u542b\u4e49\u7c7b\u4f3c\uff1a\u9898\u76ee\u3001\u8981\u6c42\u89e3\u7684\u5185\u5bb9\u3001\u9898\u5e72\u4e2d\u7684\u7591\u95ee\u53e5\u8fd9\u6837\u7684\u6982\u5ff5\u3002\u72b6\u6001\u8868\u793a\u6211\u4eec\u5728\u6c42\u89e3\u95ee\u9898\u4e4b\u4e2d\u5bf9\u95ee\u9898\u7684\u5206\u6790\u8f6c\u5316\u3002<\/p>\n\n\n\n

    \u7b2c\u4e00\u6b65\uff1a\u72b6\u6001\u7684\u5b9a\u4e49<\/h3>\n\n\n\n

    \u6709\u7684\u95ee\u9898\u8fc7\u4e8e\u62bd\u8c61\uff0c\u6216\u8005\u8fc7\u4e8e\u5570\u55e6\u5e72\u6270\u6211\u4eec\u89e3\u9898\u7684\u601d\u8def\uff0c\u6211\u4eec\u8981\u505a\u7684\u5c31\u662f\u5c06\u9898\u5e72\u4e2d\u7684\u95ee\u9898\u8fdb\u884c\u8f6c\u5316\uff08\u6362\u4e00\u79cd\u8bf4\u6cd5\uff0c\u542b\u4e49\u4e0d\u53d8\uff09\u3002\u8f6c\u5316\u6210\u4e00\u7cfb\u5217\u540c\u7c7b\u95ee\u9898\u7684\u67d0\u4e2a\u89e3\u7684\u60c5\u51b5\uff0c\u6bd4\u5982\u8bf4\uff1a<\/p>\n\n\n\n

    \u9898\u76ee\uff1a\u6c42\u4e00\u4e2a\u6570\u5217\u4e2d\u6700\u5927\u8fde\u7eed\u5b50\u5e8f\u5217\u7684\u548c\u3002<\/p><\/blockquote>\n\n\n\n

    \u6211\u4eec\u8981\u5c06\u8fd9\u4e2a\u539f\u95ee\u9898\u8f6c\u5316\u4e3a\uff1a<\/p>\n\n\n\n

    \u72b6\u6001\u5b9a\u4e49\uff1aFk<\/sub>\u662f\u7b2ck\u9879\u524d\u7684\u6700\u5927\u5e8f\u5217\u548c\uff0c\u6c42F1<\/sub>\uff5eFN<\/sub>\u4e2d\u6700\u5927\u503c\u3002<\/p><\/blockquote>\n\n\n\n

    \u901a\u8fc7\u6362\u4e00\u79cd\u8868\u8ff0\u65b9\u5f0f\uff0c\u6211\u4eec\u6e05\u6670\u7684\u53d1\u73b0\u4e86\u89e3\u51b3\u95ee\u9898\u7684\u601d\u8def\uff0c\u5982\u4f55\u6c42\u51faF1<\/sub>\uff5eFN<\/sub>\u4e2d\u7684\u6700\u5927\u503c\u662f\u89e3\u51b3\u539f\u95ee\u9898\u7684\u5173\u952e\u90e8\u5206\u3002\u4e0a\u8ff0\u5c06\u539f\u95ee\u9898\u8f6c\u5316\u6210\u53e6\u4e00\u79cd\u8868\u8ff0\u65b9\u5f0f\u7684\u8fc7\u7a0b\u53eb\u505a\uff1a\u72b6\u6001\u7684\u5b9a\u4e49\u3002\u8fd9\u6837\u7684\u72b6\u6001\u5b9a\u4e49\u7ed9\u51fa\u4e86\u4e00\u79cd\u7c7b\u4f3c\u901a\u89e3\u7684\u601d\u8def\uff0c\u628a\u4e00\u4e2a\u539f\u6765\u6beb\u65e0\u5934\u7eea\u7684\u95ee\u9898\u8f6c\u6362\u6210\u4e86\u53ef\u4ee5\u6c42\u89e3\u7684\u95ee\u9898\u3002<\/p>\n\n\n\n

    \u7b2c\u4e8c\u6b65\uff1a\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u5b9a\u4e49<\/h3>\n\n\n\n

    \u5728\u8fdb\u884c\u4e86\u72b6\u6001\u7684\u5b9a\u4e49\u540e\uff0c\u81ea\u7136\u800c\u7136\u7684\u60f3\u5230\u53bb\u6c42\u89e3F1<\/sub>\uff5eFN<\/sub>\u4e2d\u6700\u5927\u503c\u3002\u8fd9\u4e5f\u662f\u72b6\u6001\u5b9a\u4e49\u7684\u4f5c\u7528\uff0c\u8ba9\u6211\u4eec\u628a\u4e00\u4e2a\u603b\u4f53\u7684\u95ee\u9898\u8f6c\u5316\u6210\u4e00\u7cfb\u5217\u95ee\u9898\uff0c\u800c\u7b2c\u4e8c\u6b65\uff1a\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u5b9a\u4e49\u5219\u544a\u8bc9\u6211\u4eec\u5982\u4f55\u53bb\u6c42\u89e3\u4e00\u4e2a\u95ee\u9898\uff0c\u5bf9\u4e8e\u4e0a\u8ff0\u5df2\u7ecf\u8f6c\u6362\u6210\u4e00\u7cfb\u5217\u95ee\u9898\u6211\u4eec\u8981\u5173\u6ce8\u7684\u70b9\u5c31\u5728\u4e8e\uff1a\u5982\u4f55\u80fd\u591f\u7528\u524d\u4e00\u9879\u6216\u8005\u524d\u51e0\u9879\u7684\u4fe1\u606f\u5f97\u5230\u4e0b\u4e00\u9879\uff0c\u8fd9\u79cd\u4ece\u6700\u4f18\u5b50\u72b6\u6001\u8f6c\u6362\u4e3a\u4e0b\u4e00\u4e2a\u6700\u4f18\u72b6\u6001\u7684\u601d\u8def\u5c31\u662f\u52a8\u6001\u89c4\u5212\u7684\u6838\u5fc3\u3002 
    \u5bf9\u4e8e\u4e0a\u9762\u7684\u4f8b\u5b50\u9898\u76ee\u6765\u8bf4\uff0c\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u7684\u5b9a\u4e49\u5e94\u8be5\u662f\uff1a<\/p>\n\n\n\n

    Fk<\/sub>=max{Fk-1<\/sub>+Ak<\/sub>,Ak<\/sub>} 
    Fk<\/sub>\u662f\u524dk\u9879\u7684\u548c\uff0cAk<\/sub>\u662f\u7b2ck\u9879\u7684\u503c<\/p><\/blockquote>\n\n\n\n

    \u4ed4\u7ec6\u601d\u8003\u4e00\u756a\uff0c\u6211\u4eec\u80fd\u591f\u5f97\u5230\u8fd9\u6837\u7684\u7ed3\u8bba\uff0c\u5bf9\u4e8e\u524dk\u4e2a\u9879\u7684\u6700\u5927\u5b50\u5e8f\u5217\u548c\u662f\u524dk-1\u9879\u7684\u6700\u5927\u5b50\u5e8f\u5217\u548cFk<\/sub>\u4e0e\u7b2ck\u9879\u7684\u548c\u3001\u6216\u8005\u7b2ck\u9879\u4e24\u8005\u4e2d\u8f83\u5927\u7684\u3002\u5982\u679c\u5927\u5bb6\u8fd8\u662f\u4e0d\u80fd\u7406\u89e3\u8fd9\u4e2a\u539f\u7406\u5efa\u8bae\u7528\u6f14\u7b97\u7eb8\u81ea\u5df1\u8ba1\u7b97\u4e00\u756a\uff0c\u8fd9\u91cc\u5c31\u4e0d\u8fc7\u591a\u8d58\u8ff0\u4e86\u3002\u8fd9\u79cd\u72b6\u6001\u8f6c\u79fb\u7684\u601d\u8def\u5c31\u662fDP\u7684\u6838\u5fc3\u3002<\/p>\n\n\n\n

    \u52a8\u6001\u89c4\u5212\u7684\u5e94\u7528\u573a\u666f<\/h2>\n\n\n\n
    \n\n\n\n

    \u770b\u8fc7\u4e86\u5982\u4f55\u53bb\u4f7f\u7528\u52a8\u6001\u89c4\u5212\uff0c\u90a3\u4e48\u968f\u4e4b\u800c\u6765\u7684\u95ee\u9898\u5c31\u5728\u4e8e\uff1a\u65e2\u7136\u52a8\u6001\u89c4\u5212\u4e0d\u662f\u67d0\u4e2a\u56fa\u5b9a\u7684\u7b97\u6cd5\uff0c\u800c\u662f\u4e00\u79cd\u7b56\u7565\u601d\u8def\uff0c\u90a3\u4e48\u4ec0\u4e48\u65f6\u5019\u5e94\u8be5\u53bb\u4f7f\u7528\u4ec0\u4e48\u65f6\u5019\u4e0d\u80fd\u7528\u5462\uff1f\u7b54\u6848\u5f88\u7b80\u77ed\uff1a<\/p>\n\n\n\n

    \u5bf9\u4e8e\u4e00\u4e2a\u53ef\u62c6\u5206\u95ee\u9898\u4e2d\u5b58\u5728\u53ef\u4ee5\u7531\u524d\u82e5\u5e72\u9879\u8ba1\u7b97\u5f53\u524d\u9879\u7684\u95ee\u9898\u53ef\u4ee5\u7531\u52a8\u6001\u89c4\u5212\u8ba1\u7b97\u3002 <\/p>\n\n\n\n

    \u4f8b\u98981: \u6570\u5854\u53d6\u6570\u95ee\u9898<\/h2>\n\n\n\n

    \u4e00\u4e2a\u9ad8\u5ea6\u4e3aN\u7684\u7531\u6b63\u6574\u6570\u7ec4\u6210\u7684\u4e09\u89d2\u5f62\uff0c\u4ece\u4e0a\u8d70\u5230\u4e0b\uff0c\u6c42\u7ecf\u8fc7\u7684\u6570\u5b57\u548c\u7684\u6700\u5927\u503c\u3002 
    \u6bcf\u6b21\u53ea\u80fd\u8d70\u5230\u4e0b\u4e00\u5c42\u76f8\u90bb\u7684\u6570\u4e0a\uff0c\u4f8b\u5982\u4ece\u7b2c3\u5c42\u76846\u5411\u4e0b\u8d70\uff0c\u53ea\u80fd\u8d70\u5230\u7b2c4\u5c42\u76842\u62169\u4e0a\u3002<\/p>\n\n\n\n

    \u8be5\u4e09\u89d2\u5f62\u7b2cn\u5c42\u6709n\u4e2a\u6570\u5b57\uff0c\u4f8b\u5982\uff1a<\/p>\n\n\n\n

    \u7b2c\u4e00\u5c42\u6709\u4e00\u4e2a\u6570\u5b57\uff1a5<\/p>\n\n\n\n

    \u7b2c\u4e8c\u5c42\u6709\u4e24\u4e2a\u6570\u5b57\uff1a8 4<\/p>\n\n\n\n

    \u7b2c\u4e09\u5c42\u6709\u4e09\u4e2a\u6570\u5b57\uff1a3 6 9<\/p>\n\n\n\n

    \u7b2c\u56db\u5c42\u6709\u56db\u4e2a\u6570\u5b57\uff1a7 2 9 5<\/p>\n\n\n\n

    \u6700\u4f18\u65b9\u6848\u662f\uff1a5 + 8 + 6 + 9 = 28<\/p>\n\n\n\n

    \u6ce8\u610f:\u4e0a\u9762\u5e94\u8be5\u662f\u6392\u5217\u6210\u4e00\u4e2a\u4e09\u89d2\u5f62\u7684\u6837\u5b50\u4e0d\u662f\u7ad6\u5411\u5bf9\u5e94\u7684\uff0c\u6392\u7248\u95ee\u9898\u6ca1\u6709\u663e\u793a\u6210\u4e09\u89d2\u5f62\u3002<\/p>\n\n\n\n

    \u72b6\u6001\u5b9a\u4e49: Fi\uff0cj<\/sub>\u662f\u7b2ci\u884cj\u5217\u9879\u6700\u5927\u53d6\u6570\u548c\uff0c\u6c42\u7b2cn\u884cFn\uff0cm<\/sub>\uff080 < m < n\uff09\u4e2d\u6700\u5927\u503c\u3002<\/p>\n\n\n\n

    \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1aFi\uff0cj<\/sub>\u00a0= max{Fi-1,j-1<\/sub>,Fi-1,j<\/sub>}+Ai,jt<\/sub><\/p>\n\n\n\n

    \n\nimport java.util.Scanner;\n\npublic class Dp01 {\n    public static void main(String[] args) {\n        Scanner scan = new Scanner(System.in);\n\n        int n = scan.nextInt();\n        long max = 0;\n        int[][] dp = new int[n][n];\n        dp[0][0] = scan.nextInt();\n\n        for(int i=1;i<n;i++){\n            for(int j=0;j<=i;j++){\n                int num = scan.nextInt();\n                if(j==0){\n                    dp[i][j] = dp[i-1][j] + num;\n                }else {\n                    dp[i][j] = Math.max(dp[i-1][j-1],dp[i - 1][j])+num;\n                }\n                max = Math.max(dp[i][j],max);\n            }\n        }\n        System.out.println(max);\n    }\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98982:\u7f16\u8f91\u8ddd\u79bb<\/h2>\n\n\n\n
    \u7f16\u8f91\u8ddd\u79bb\uff0c\u53c8\u79f0Levenshtein\u8ddd\u79bb\uff08\u4e5f\u53eb\u505aEdit Distance\uff09\uff0c\u662f\u6307\u4e24\u4e2a\u5b57\u4e32\u4e4b\u95f4\uff0c\u7531\u4e00\u4e2a\u8f6c\u6210\u53e6\u4e00\u4e2a\u6240\u9700\u7684\u6700\u5c11\u7f16\u8f91\u64cd\u4f5c\u6b21\u6570\u3002\u8bb8\u53ef\u7684\u7f16\u8f91\u64cd\u4f5c\u5305\u62ec\u5c06\u4e00\u4e2a\u5b57\u7b26\u66ff\u6362\u6210\u53e6\u4e00\u4e2a\u5b57\u7b26\uff0c\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\uff0c\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u3002 
    \u4f8b\u5982\u5c06kitten\u4e00\u5b57\u8f6c\u6210sitting\uff1a 
    sitten \uff08k->s\uff09 
    sittin \uff08e->i\uff09 
    sitting \uff08->g\uff09 
    \u6240\u4ee5kitten\u548csitting\u7684\u7f16\u8f91\u8ddd\u79bb\u662f3\u3002\u4fc4\u7f57\u65af\u79d1\u5b66\u5bb6Vladimir Levenshtein\u57281965\u5e74\u63d0\u51fa\u8fd9\u4e2a\u6982\u5ff5\u3002 
    \u7ed9\u51fa\u4e24\u4e2a\u5b57\u7b26\u4e32a,b\uff0c\u6c42a\u548cb\u7684\u7f16\u8f91\u8ddd\u79bb\u3002<\/p>\n\n\n\n
    \u72b6\u6001\u5b9a\u4e49:Fi,j<\/sub>\u8868\u793a\u7b2c\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\u524di\u4e2a\u5b57\u6bcd\u548c\u7b2c\u4e8c\u4e2a\u5b57\u7b26\u4e32\u7684\u524dj\u4e2a\u5b57\u6bcd\u9700\u8981\u7f16\u8f91\u7684\u6b21\u6570\uff0c\u6c42Fn,m<\/sub>\uff0cn\u548cm\u5206\u522b\u662f\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\u3002<\/p>\n\n\n\n
    \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\uff1a 
    \u5f53Fi,j-1<\/sub>=Fi-1,j<\/sub>\u65f6\uff0cFi,j<\/sub>=Fi,j-1<\/sub>\uff1b 
    \u5f53Fi,j-1<\/sub>\uff01=Fi-1,j<\/sub>\u65f6\uff0cFi,j<\/sub>=min{Fi-1,j-1<\/sub>,Fi,j-1<\/sub>,Fi-1,j<\/sub>}+1.<\/p>\n\n\n\n
    package com.hust0328;\n\nimport java.util.Scanner;\n\n\/**\n * Created by huststl on 2018\/3\/28 14:44\n * \u52a8\u6001\u89c4\u521202\n *\/\npublic class dp02 {\n    public static void main(String[] args) {\n        Scanner scan = new Scanner(System.in);\n        String aStr = scan.nextLine();\n        String bStr = scan.nextLine();\n        int aLen = aStr.length();\n        int bLen = bStr.length();\n        int[][] dp = new int[aLen+1][bLen+1];\n        for(int i=0;i<aLen+1;i++){\n            dp[i][0] = i;\n        }\n        for(int i=0;i<bLen+1;i++){\n            dp[0][i] = i;\n        }\n        for(int i=1;i<aLen+1;i++){\n            for(int j=1;j<bLen+1;j++){\n                if(aStr.charAt(i-1) == bStr.charAt(j-1)){\n                    dp[i][j] = dp[i-1][j-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        System.out.println(dp[aLen][bLen]);\n    }\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98983:\u77e9\u9635\u53d6\u6570\u95ee\u9898<\/h2>\n\n\n\n
    \u4e00\u4e2aN*N\u77e9\u9635\u4e2d\u6709\u4e0d\u540c\u7684\u6b63\u6574\u6570\uff0c\u7ecf\u8fc7\u8fd9\u4e2a\u683c\u5b50\uff0c\u5c31\u80fd\u83b7\u5f97\u76f8\u5e94\u4ef7\u503c\u7684\u5956\u52b1\uff0c\u4ece\u5de6\u4e0a\u8d70\u5230\u53f3\u4e0b\uff0c\u53ea\u80fd\u5411\u4e0b\u5411\u53f3\u8d70\uff0c\u6c42\u80fd\u591f\u83b7\u5f97\u7684\u6700\u5927\u4ef7\u503c\u3002\u4f8b\u5982\uff1a3 * 3\u7684\u65b9\u683c\u3002<\/p>\n\n\n\n
    1 3 3 
    2 1 3 
    2 2 1<\/p>\n\n\n\n
    \u80fd\u591f\u83b7\u5f97\u7684\u6700\u5927\u4ef7\u503c\u4e3a\uff1a11<\/p>\n\n\n\n
    public static void main(String[] args) {\n    int n=5;\n\n    int[][] arr={{1,3,3},{2,1,3},{2,6,1},{3,2,3}};\n\n    printArr(arr);\n    for(int i=0;i<arr.length;i++){\n        for(int j=0;j<arr[0].length;j++){\n            if (i==0){\n                if (j==0){\n                    continue;\n                }else {\n                    arr[i][j]=arr[i][j-1]+arr[i][j];\n                }\n            }else {\n                if (j==0){\n                    arr[i][j]=arr[i-1][j]+arr[i][j];\n                }else {\n                    arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1])+arr[i][j];\n                }\n            }\n\n        }\n    }\n    printArr(arr);\n\n}\nprivate static void printArr(int[][] dp) {\n    System.out.println(\"--------\");\n    for(int i=0;i<dp.length;i++){\n        for(int j=0;j<dp[0].length;j++){\n            System.out.print(dp[i][j]+\",\");\n        }\n        System.out.println();\n    }\n    System.out.println(\"--------\");\n\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98984:\u80cc\u5305\u95ee\u9898<\/h2>\n\n\n\n
    \u5728N\u4ef6\u7269\u54c1\u53d6\u51fa\u82e5\u5e72\u4ef6\u653e\u5728\u5bb9\u91cf\u4e3aW\u7684\u80cc\u5305\u91cc\uff0c\u6bcf\u4ef6\u7269\u54c1\u7684\u4f53\u79ef\u4e3aW1\uff0cW2\u2026\u2026Wn\uff08Wi\u4e3a\u6574\u6570\uff09\uff0c\u4e0e\u4e4b\u76f8\u5bf9\u5e94\u7684\u4ef7\u503c\u4e3aP1,P2\u2026\u2026Pn\uff08Pi\u4e3a\u6574\u6570\uff09\u3002\u6c42\u80cc\u5305\u80fd\u591f\u5bb9\u7eb3\u7684\u6700\u5927\u4ef7\u503c\u3002<\/p>\n\n\n\n
    public static void main(String[] args) {\n\n    int[] weight = {0,2,3,1,4};\n    int[] price = {0,4,2,3,2};\n    int[][] F = getMaxValue(weight, price);\n    System.out.println(\"\u80cc\u5305\u627f\u91cd\u4ece0\u5230\u6240\u6709\u7269\u54c1\u91cd\u91cf\u4e4b\u548c\u4e3a10\u7684\u627f\u91cd\u80fd\u591f\u8fbe\u5230\u7684\u6700\u5927\u4ef7\u503c\u5206\u522b\u4e3a\uff1a\");\n    for(int i = 0;i < F.length;i++) {\n        for(int j = 0;j < F[0].length;j++)\n            System.out.print(F[i][j]+\"\\t\");\n        System.out.println();\n    }\n}\npublic static int[][] getMaxValue(int[] weight, int[] value) {\n    int lenRow = weight.length;\n    int lenColumn = 0;\n    for(int i = 0;i < weight.length;i++)\n        lenColumn += weight[i];\n    int[][] F = new int[lenRow][lenColumn+1]; \/\/\u5217\u503c\u957f\u5ea6\u52a01\uff0c\u662f\u56e0\u4e3a\u6700\u540e\u4e00\u5217\u8981\u4fdd\u8bc1\u91cd\u91cf\u503c\u4e3alenColumn\n    for(int i = 1;i < weight.length;i++) {\n        for(int j = 1;j <= lenColumn;j++) {\n            if(weight[i]<=j) { \/\/\u91cd\u91cf\u6bd4\u8fd9\u4e2a\u72b6\u6001\u5c0f\uff0c\u90a3\u4e48\u5c31\u80fd\u653e\u3002 \u90a3\u4e48\u5c31\u53ea\u662f\u653e\u4e0e\u4e0d\u653e\uff0c\u770b\u662f\u653e\u91cd\u91cf\u5927\uff0c\u8fd8\u662f\u4e0d\u653e\u91cd\u91cf\u5927\n                F[i][j] = Math.max(F[i-1][j], F[i-1][j-weight[i]]+value[i]);\n            }else {\n                F[i][j] = F[i-1][j];\/\/\u7b2ci\u4ef6\u7269\u54c1\u4e0d\u80fd\u653e\n            }\n        }\n    }\n    return F;\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98985:\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/h2>\n\n\n\n
    \u7ed9\u51fa\u957f\u5ea6\u4e3aN\u7684\u6570\u7ec4\uff0c\u627e\u51fa\u8fd9\u4e2a\u6570\u7ec4\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u3002 
    (\u9012\u589e\u5b50\u5e8f\u5217\u662f\u6307\uff0c\u5b50\u5e8f\u5217\u7684\u5143\u7d20\u662f\u9012\u589e\u7684\uff09 
    \u4f8b\u5982\uff1a5 1 6 8 2 4 5 10\uff0c\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u662f1 2 4 5 10<\/p>\n\n\n\n
    package com.hust0328;\n\nimport java.util.Scanner;\n\n\/**\n * Created by huststl on 2018\/3\/28 15:18\n * \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\n *\/\npublic class Dp05 {\n    public static void main(String[] args) {\n        Scanner scan = new Scanner(System.in);\n        int n = scan.nextInt();\n        int[] num = new int[n];\n        for(int i=0;i<n;i++){\n            num[i] = scan.nextInt();\n        }\n        double[] dou = new double[n+1];\n        dou[0] = Integer.MIN_VALUE;\n        dou[1] = num[0];\n        int Len = 1;\n        int p,r,m;\n        for(int i=1;i<n;i++){\n            p = 0;\n            r = Len;\n            while (p<=r){\n                m = (p+r)\/2;\n                if(dou[m] < num[i]){\n                    p = m+1;\n                }else {\n                    r = m-1;\n                }\n            }\n            dou[p] = num[i];\n            if(p>Len){\n                Len++;\n            }\n        }\n        System.out.println(Len);\n     }\n}<\/code><\/pre>\n\n\n\n
    public static void main(String[] args) {\n      int[] num = {5,1,3,6,7,2,11,8,9,4,5,10};\n    \/\/  int[] num = {6,7,7,7,8,8,7,6,5,4,7,7,6,1,2,3,1,9,9,9,9,9,1};\n    \/\/  int[] num = {1,2,3,1,3};\n\n    \/\/vec\u5b58\u653e\u9012\u589e\u5b50\u5e8f\u5217\n    List<Integer> vec=new ArrayList<>();\n    \/\/maxLen\u6570\u7ec4\u91cc\u5b58\u653e\u4ee5\u5143\u7d20i\u7ed3\u5c3e\u7684\u6700\u5927\u9012\u589e\u5b50\u5e8f\u5217\u957f\u5ea6\n    int[] maxLen=new int[num.length];\n\n    vec.add(num[0]);\n    maxLen[0]=1;\n    int max=1;\n    out:for(int i=1;i<num.length;i++){\n        for(int j=0;j<vec.size();j++){\n            \/\/\u5728vec\u4e2d\u67e5\u627e\u5927\u4e8e\u7b49\u4e8enum[i]\u7684\u7b2c\u4e00\u4e2a\u5143\u7d20\u5e76\u66ff\u6362\u6389\uff0c\u5e76\u66f4\u65b0maxLen[i]\uff0cnum\u4e2d\u7b2ci\u4e2a\u5143\u7d20\u7ed3\u5c3e\u7684\u6700\u5927\u9012\u589e\u5b50\u5e8f\u5217\u957f\u5ea6\u4e3aj+1;\n\n            if (vec.get(j)>num[i]){\n                vec.remove(j);\n                vec.add(j,num[i]);\n                maxLen[i]=j+1;\n                \/\/ \u627e\u5230\u540e\u7ee7\u7eed\u4e0b\u4e00\u4e2a\u5916\u5faa\u73af\u3002\n                continue out;\n            }\n        }\n        \/\/\u5982\u679cnum[i] \u6bd4vec\u4e2d\u6240\u4ee5\u5143\u7d20\u90fd\u5927\uff0c\u5c31\u6dfb\u52a0\u5230vec\u4e2d\u672b\u5c3e\uff0c\u5e76\u5c06maxLen[i]\u8bbe\u7f6e\u4e3avec\u7684\u5927\u5c0f\u3002\n        vec.add(num[i]);\n        maxLen[i]=vec.size();\n        max=Math.max(max, maxLen[i]);\n\n    }\n    System.out.println(JSON.toJSON(num));\n\n    System.out.println(vec);\n\n    System.out.println(JSON.toJSON(maxLen));\n    System.out.println(max);\n\n    Integer[] maxArr=new Integer[max];\n\n    int j=maxLen.length-1;\n\n    for(int i=max-1;i>=0;i--){\n        for(;j>=0;j--){\n            if (maxLen[j]==i+1){\n                maxArr[i]=num[j];\n                break;\n            }\n        }\n    }\n    System.out.println(JSON.toJSON(maxArr));\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98986:\u6700\u5927\u5b50\u6bb5\u548c<\/h2>\n\n\n\n
    N\u4e2a\u6574\u6570\u7ec4\u6210\u7684\u5e8f\u5217a[1],a[2],a[3],\u2026,a[n]\uff0c\u6c42\u8be5\u5e8f\u5217\u5982a[i]+a[i+1]+\u2026+a[j]\u7684\u8fde\u7eed\u5b50\u6bb5\u548c\u7684\u6700\u5927\u503c\u3002 
    \u5f53\u6240\u7ed9\u7684\u6574\u6570\u5747\u4e3a\u8d1f\u6570\u65f6\u548c\u4e3a0\u3002 
    \u4f8b\u5982\uff1a-2,11,-4,13,-5,-2\uff0c\u548c\u6700\u5927\u7684\u5b50\u6bb5\u4e3a\uff1a11,-4,13\u3002\u548c\u4e3a20<\/p>\n\n\n\n
    package com.hust0328;\n\/**\n * Created by huststl on 2018\/3\/28 15:33\n * \u6700\u5927\u5b50\u6bb5\u548c\n *\/\npublic class Dp06 {\n   public static int maxSubSum1(int []a){\n        int maxSum=0; int nowSum=0;\n        for(int i=0;i<a.length;i++){\n            nowSum=nowSum+a[i];\n            if(nowSum>maxSum){\/\/\u66f4\u65b0\u6700\u5927\u5b50\u6bb5\u548c\n                maxSum=nowSum;\n            }\n            if(nowSum<0){\/\/\u5f53\u5f53\u524d\u7d2f\u52a0\u548c\u4e3a\u8d1f\u6570\u65f6\u820d\u5f03\uff0c\u91cd\u7f6e\u4e3a0\n                nowSum=0;\n            }\n        }\n        return maxSum;\n    }\n    public static void main(String[] args) {\n        int a[]={-2,11,-4,13,-5,-2};\n        System.out.println(maxSubSum1(a));\n\n\n    }\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98987:\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217Lcs<\/h2>\n\n\n\n
    \u7ed9\u51fa\u4e24\u4e2a\u5b57\u7b26\u4e32A B\uff0c\u6c42A\u4e0eB\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\uff08\u5b50\u5e8f\u5217\u4e0d\u8981\u6c42\u662f\u8fde\u7eed\u7684\uff09\u3002 
    \u6bd4\u5982\u4e24\u4e2a\u4e32\u4e3a\uff1a<\/p>\n\n\n\n
    abcicba 
    abdkscab<\/p>\n\n\n\n
    ab\u662f\u4e24\u4e2a\u4e32\u7684\u5b50\u5e8f\u5217\uff0cabc\u4e5f\u662f\uff0cabca\u4e5f\u662f\uff0c\u5176\u4e2dabca\u662f\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u6700\u957f\u7684\u5b50\u5e8f\u5217\u3002<\/p>\n\n\n\n
    package com.hust0328;\n\nimport java.util.Scanner;\n\n\/**\n * Created by huststl on 2018\/3\/28 15:55\n * \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217Lcs\n *\/\npublic class Dp07 {\n    public static void main(String[] args) {\n        Scanner scan = new Scanner(System.in);\n        String aStr = scan.nextLine();\n        String bStr = scan.nextLine();\n        int aLen = aStr.length();\n        int bLen = bStr.length();\n        int[][] dp = new int[aLen+1][bLen+1];\n        for(int i=1;i<aLen+1;i++){\n            for(int j=1;j<bLen+1;j++){\n                if(dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)\n                        && dp[i - 1][j] == dp[i - 1][j - 1]){\n                    dp[i][j] = dp[i-1][j]+1;\n                }else {\n                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);\n                }\n            }\n        }\n        int max = dp[aLen][bLen];\n        StringBuilder sb = new StringBuilder(128);\n        while (max>0){\n            if(dp[aLen-1][bLen] == dp[aLen][bLen-1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]){\n                sb.append(aStr.charAt(aLen-1));\n                max--;\n                aLen--;\n                bLen--;\n            }else {\n                if(dp[aLen][bLen-1] == dp[aLen][bLen]){\n                    bLen--;\n                }else {\n                    aLen--;\n                }\n            }\n            System.out.println(sb.reverse().toString());\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
    public static void main(String[] args) {\n        String s2=\"1A2C3D4B56\";\n        String s1=\"B1D23CA45B6A\";\n\n        String[][] dp= new String[s1.length()+1][s2.length()+1];\n        for(int i=0;i<=s1.length();i++)\n            dp[i][0] = \"\";\n        for(int i=0;i<=s2.length();i++)\n            dp[0][i] = \"\";\n\n        for(int i=1;i<=s1.length();i++){\n            for(int j=1;j<=s2.length();j++){\n                if(s1.charAt(i-1)==s2.charAt(j-1)) {\n                    dp[i][j] = dp[i-1][j-1]+s1.charAt(i-1);\n                }else{\n                    dp[i][j] = dp[i-1][j].length()>dp[i][j-1].length()?dp[i-1][j]:dp[i][j-1];\n                }\n            }\n        }\n        printArr(dp);\n        String result=dp[s1.length()][s2.length()]==\"\"?\"-1\":dp[s1.length()][s2.length()];\n\n\n        System.out.print(result);\n    }\n    private static void printArr(Object[][] dp) {\n        System.out.println(\"--------\");\n        for(int i=0;i<dp.length;i++){\n            for(int j=0;j<dp[0].length;j++){\n                System.out.print(dp[i][j]+\",\");\n            }\n            System.out.println();\n        }\n        System.out.println(\"--------\");\n\n    }<\/code><\/pre>\n\n\n\n
    \u4f8b\u98988:\u6b63\u6574\u6570\u5206\u7ec4<\/h2>\n\n\n\n
    \u5c06\u4e00\u5806\u6b63\u6574\u6570\u5206\u4e3a2\u7ec4\uff0c\u8981\u6c422\u7ec4\u7684\u548c\u76f8\u5dee\u6700\u5c0f\u3002 
    \u4f8b\u5982\uff1a1 2 3 4 5\uff0c\u5c061 2 4\u5206\u4e3a1\u7ec4\uff0c3 5\u5206\u4e3a1\u7ec4\uff0c\u4e24\u7ec4\u548c\u76f8\u5dee1\uff0c\u662f\u6240\u6709\u65b9\u6848\u4e2d\u76f8\u5dee\u6700\u5c11\u7684\u3002<\/p>\n\n\n\n
     \u601d\u8def\uff1a<\/p>\n\n\n\n
    \u5148\u628a\u6570\u636e\u5206\u6210\u4e24\u7ec4\uff0c\u90a3\u4e48\u5fc5\u5b9a\u6709\u4e00\u7ec4\u8d8b\u8fd1\u4e8e\u6240\u6709\u6570\u7684\u548c\/2<\/p>\n\n\n\n
    \u6211\u4eec\u53ef\u4ee5\u628a\u6570\u7684\u548c\u770b\u6210\u5305\u7684\u91cd\u91cf\uff0c\u6bcf\u4e2a\u6570\u770b\u6210\u8981\u653e\u5165\u5305\u7684\u7269\u4f53\uff0c\u8fd9\u6837\u5c31\u80fd\u628a\u95ee\u9898\u5f53\u4f5c01\u80cc\u5305\u5904\u7406\uff0c\u627e\u5230\u5c0f\u4e8esum\/2\u7684\u6700\u5927\u653e\u5165\u91cf\u5373\u53ef<\/p>\n\n\n\n
    dp[i][j]\u4ee3\u8868\u653e\u5165\u5230\u7b2ci\u4e2a\u7269\u4f53\u65f6\u80cc\u5305\u5bb9\u91cf\u4e3aj\u65f6\u6570\u7684\u548c\uff0c\u90a3\u4e48dp[i][j]\u5927\u5c0f\u7531\u524d\u4e00\u4e2a\u7269\u4f53\u653e\u6216\u4e0d\u653e\u51b3\u5b9a<\/p>\n\n\n\n
    \u53ef\u4ee5\u5f97\u5230dp[i][j] = max(dp[i – 1][j], dp[i – 1][j-a[i]] + a[i])<\/p>\n\n\n\n
    \u6700\u540e\u5f97\u5230dp[n][sum\/2]\u8868\u793a\u8f83\u5c0f\u7684\u90a3\u4e00\u7ec4\u6570\u4e4b\u548c\uff0c\u90a3\u4e48\u4e24\u7ec4\u6570\u548c\u4e4b\u5dee\u5c31\u662f(sum – dp[n][sum\/2])-dp[n][sum \/ 2]<\/p>\n\n\n\n
    package com.hust0328;\n\nimport java.util.Scanner;\n\n\/**\n * Created by huststl on 2018\/3\/28 16:18\n * \u6b63\u6574\u6570\u5206\u7ec4\n *\/\npublic class dp08 {\n    public static void main(String[] args) {\n        Scanner scan = new Scanner(System.in);\n        int n = scan.nextInt();\n        long sum = 0,max = 0;\n        int[] nums = new int[n];\n        for(int i=0;i < n;i++){\n            nums[i]= scan.nextInt();\n            sum += nums[i];\n        }\n        int[] dp = new int[(int)(sum\/2+1)];\n        for(int i=0;i<n;i++){\n            for(int j = (int) (sum \/ 2); j > 0; j--){\n                if(j >=nums[i]){\n                    dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);\n                }\n            }\n\n        }\n        for(int i=1;i<sum\/2+1;i++){\n            max = max >dp[i]?max:dp[i];\n        }\n        System.out.println(Math.abs((sum-max)-max));\n\n    }\n}<\/code><\/pre>\n\n\n\n
    \u4f8b\u98989:\u6b63\u5219\u5339\u914d<\/strong><\/h2>\n\n\n\n
    \u8bf7\u5b9e\u73b0\u4e00\u4e2a\u51fd\u6570\u7528\u6765\u5339\u914d\u5305\u542b'. '<\/code>\u548c'*'<\/code>\u7684\u6b63\u5219\u8868\u8fbe\u5f0f\u3002\u6a21\u5f0f\u4e2d\u7684\u5b57\u7b26'.'<\/code>\u8868\u793a\u4efb\u610f\u4e00\u4e2a\u5b57\u7b26\uff0c\u800c'*'<\/code>\u8868\u793a\u5b83\u524d\u9762\u7684\u5b57\u7b26\u53ef\u4ee5\u51fa\u73b0\u4efb\u610f\u6b21\uff08\u542b0\u6b21\uff09\u3002\u5728\u672c\u9898\u4e2d\uff0c\u5339\u914d\u662f\u6307\u5b57\u7b26\u4e32\u7684\u6240\u6709\u5b57\u7b26\u5339\u914d\u6574\u4e2a\u6a21\u5f0f\u3002\u4f8b\u5982\uff0c\u5b57\u7b26\u4e32\"aaa\"<\/code>\u4e0e\u6a21\u5f0f\"a.a\"<\/code>\u548c\"ab*ac*a\"<\/code>\u5339\u914d\uff0c\u4f46\u4e0e\"aa.a\"<\/code>\u548c\"ab*a\"<\/code>\u5747\u4e0d\u5339\u914d\u3002<\/p>\n\n\n\n
    \u793a\u4f8b 1:<\/p>\n\n\n\n
    \u8f93\u5165:\ns = \"aa\"\np = \"a\"\n\u8f93\u51fa: false\n\u89e3\u91ca: \"a\" \u65e0\u6cd5\u5339\u914d \"aa\" \u6574\u4e2a\u5b57\u7b26\u4e32\u3002\n<\/pre>\n\n\n\n
    \u793a\u4f8b 2:<\/p>\n\n\n\n
    \u8f93\u5165:\ns = \"aa\"\np = \"a*\"\n\u8f93\u51fa: true\n\u89e3\u91ca: \u56e0\u4e3a '*' \u4ee3\u8868\u53ef\u4ee5\u5339\u914d\u96f6\u4e2a\u6216\u591a\u4e2a\u524d\u9762\u7684\u90a3\u4e00\u4e2a\u5143\u7d20, \u5728\u8fd9\u91cc\u524d\u9762\u7684\u5143\u7d20\u5c31\u662f 'a'\u3002\u56e0\u6b64\uff0c\u5b57\u7b26\u4e32 \"aa\" \u53ef\u88ab\u89c6\u4e3a 'a' \u91cd\u590d\u4e86\u4e00\u6b21\u3002\n<\/pre>\n\n\n\n
    \u793a\u4f8b 3:<\/p>\n\n\n\n
    \u8f93\u5165:\ns = \"ab\"\np = \".*\"\n\u8f93\u51fa: true\n\u89e3\u91ca: \".*\" \u8868\u793a\u53ef\u5339\u914d\u96f6\u4e2a\u6216\u591a\u4e2a\uff08'*'\uff09\u4efb\u610f\u5b57\u7b26\uff08'.'\uff09\u3002\n<\/pre>\n\n\n\n
    \u793a\u4f8b 4:<\/p>\n\n\n\n
    \u8f93\u5165:\ns = \"aab\"\np = \"c*a*b\"\n\u8f93\u51fa: true\n\u89e3\u91ca: \u56e0\u4e3a '*' \u8868\u793a\u96f6\u4e2a\u6216\u591a\u4e2a\uff0c\u8fd9\u91cc 'c' \u4e3a 0 \u4e2a, 'a' \u88ab\u91cd\u590d\u4e00\u6b21\u3002\u56e0\u6b64\u53ef\u4ee5\u5339\u914d\u5b57\u7b26\u4e32 \"aab\"\u3002\n<\/pre>\n\n\n\n
    \u793a\u4f8b 5:<\/p>\n\n\n\n
    \u8f93\u5165:\ns = \"mississippi\"\np = \"mis*is*p*.\"\n\u8f93\u51fa: false<\/pre>\n\n\n\n