{"id":287,"date":"2020-04-15T21:45:34","date_gmt":"2020-04-15T13:45:34","guid":{"rendered":"http:\/\/47.103.223.234:100\/?p=287"},"modified":"2020-04-15T21:51:05","modified_gmt":"2020-04-15T13:51:05","slug":"%e5%8c%ba%e9%97%b4dp%e4%bb%8b%e7%bb%8d","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/15\/%e5%8c%ba%e9%97%b4dp%e4%bb%8b%e7%bb%8d\/","title":{"rendered":"\u533a\u95f4dp\u4ecb\u7ecd"},"content":{"rendered":"<h3>\u533a\u95f4dp<\/h3>\n<p>\u533a\u95f4dp\u7684\u6570\u636e\u91cf\u4e00\u822c\u90fd\u662f\u4e09\u4f4d\u6570(&lt;=300)\uff0c\u7b80\u5355\u7684\u57fa\u672c\u90fd\u662f<code class=\"katex-inline\">O(n^3)<\/code>\u7684\u4f5c\u6cd5\u3002~\u96be\u70b9~\u5c31\u662f\u4e09\u5c42\u5faa\u73af\u4e2d\u6700\u91cc\u9762\u7684\u90a3\u5c42\u5faa\u73af\uff0c\u56e0\u9898\u800c\u5f02\u3002<br \/>\n\u5373\u5728\u89e3\u51b31-i\u5185\u6240\u6709\u5b50\u533a\u95f4\u7684\u95ee\u9898\u540e\uff0c\u65b0\u589e\u4e86\u4e00\u4e2a\u5143\u7d20\uff0c\u5982\u4f55\u66f4\u65b0\u533a\u95f4\u503c\u3002\u65b0\u52a0\u5165i\u540e\uff0c\u5faa\u73af\u4ecei-1\u52301\uff0c\u9006\u5411\u66f4\u65b0\u3002(dp\u91cc\u5faa\u73af\u7684\u987a\u5e8f\u4e5f\u662f\u5f88\u91cd\u8981\u554a\uff0c\u5176\u5b9e\u5c31\u662f\u770b\u533a\u95f4\u5185\u7684\u89e3\u4f9d\u8d56\u54ea\u90e8\u5206\u533a\u95f4\u7684\u4ee5\u6c42\u89e3)<\/p>\n<pre><code class=\"language-c++\">for (int i=1;i&lt;2*n;i++){\n        for (int j=i-1;j&gt;=1;j--){\n            for (int k=j;k&lt;i;k++){\n                dp[j][i] = max(dp[j][i],oper());\n            }\n        }\n    }<\/code><\/pre>\n<p>\u5f53\u6d89\u53ca\u5230\u201c\u73af\u201d\u65f6\uff0cn\u5c31\u8981\u53d8\u62102n\u4e86\u3002\u6700\u91cc\u9762\u90a3\u5c42\u5faa\u73af\u662f\u5408\u5e76\u4e24\u4e2a\u533a\u95f4\u65f6\uff0c\u5982\u4f55\u53d6\u6700\u4f18\u7684\u95ee\u9898\u3002\u82e5\u8981\u4f18\u5316\u6210O(n^2)\u7684\u4f5c\u6cd5\uff0c\u57fa\u672c\u5c31\u662f\u53ea\u80fd\u4f18\u5316\u6700\u91cc\u9762\u90a3\u5c42\u5faa\u73af\u4e86\uff0c\u770b\u9700\u8981\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u533a\u95f4dp \u533a\u95f4dp\u7684\u6570\u636e\u91cf\u4e00\u822c\u90fd\u662f\u4e09\u4f4d\u6570(&lt;=300)\uff0c\u7b80\u5355\u7684\u57fa\u672c\u90fd\u662fO(n^3)\u7684\u4f5c\u6cd5\u3002~\u96be [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[26],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/287"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=287"}],"version-history":[{"count":3,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/287\/revisions"}],"predecessor-version":[{"id":290,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/287\/revisions\/290"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}