{"id":380,"date":"2012-05-17T15:01:00","date_gmt":"2012-05-17T07:01:00","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=380"},"modified":"2020-06-06T15:01:53","modified_gmt":"2020-06-06T07:01:53","slug":"%e7%9f%a9%e9%98%b5%e7%9b%b8%e4%b9%98-%e9%80%92%e5%bd%92%e4%b8%8e%e9%9d%9e%e9%80%92%e5%bd%92%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=380","title":{"rendered":"\u77e9\u9635\u76f8\u4e58&#8211;\u9012\u5f52\u4e0e\u975e\u9012\u5f52\u5b9e\u73b0"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u77e9\u9635\u76f8\u4e58\uff0c\u975e\u9012\u5f52\n \n\/\/\u77e9\u9635\u76f8\u4e58\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test {\n\t\n\tprivate static void MatrixChain(int&#91;] p,int&#91;]&#91;] m,int &#91;]&#91;] s,int len){\n\t\tfor(int i=1;i&lt;len;i++)\n\t\t\tm&#91;i]&#91;i]=0;\n\t\tfor(int r=2;r&lt;len;r++){\n\t\t\tfor(int i=1;i&lt;=len-r;i++){\n\t\t\t\tint j=i+r-1;\n\t\t\t\tint min=Integer.MAX_VALUE;\n\t\t\t\tfor(int k=i;k&lt;j;k++){\n\t\t\t\t\tint d=m&#91;i]&#91;k]+m&#91;k+1]&#91;j]+p&#91;i-1]*p&#91;k]*p&#91;j];\n\t\t\t\t\tif(d&lt;min){\n\t\t\t\t\t\tmin=d;\n\t\t\t\t\t\ts&#91;i]&#91;j]=k;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tm&#91;i]&#91;j]=min;\n\t\t\t}\n\t\t}\n\t}\n\t\n\tprivate static void TraceBack(int i,int j,int&#91;]&#91;] s){\n\t\tif(i==j)\n\t\t\treturn;\n\t\tTraceBack(i,s&#91;i]&#91;j],s);\n\t\tTraceBack(s&#91;i]&#91;j]+1,j,s);\n\t\tSystem.out.println(\"A&#91;\"+i+\"]&#91;\"+s&#91;i]&#91;j]+\"] * \"+\"A&#91;\"+(s&#91;i]&#91;j]+1)+\"]&#91;\"+j+\"]\");\n\t}\n\t\n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;]&#91;] m=new int&#91;100]&#91;100];\n\t\tint&#91;]&#91;] s=new int&#91;100]&#91;100];\n\t\tint&#91;] p=new int&#91;]{30,35,15,5,10,20,25};\n\t\tint len=p.length;\n\t\tMatrixChain(p,m,s,len);\n\t\tTraceBack(1,len-1,s);\n\t}\n}\n \n \n\/\/\u77e9\u9635\u76f8\u4e58 \u9012\u5f52\u89e3\u6cd5\n \n\/\/\u77e9\u9635\u76f8\u4e58\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test {\n\t\n\tprivate static int MatrixChain(int&#91;] p,int&#91;]&#91;] m,int &#91;]&#91;] s,int i,int j){\n\t\tif(i==j){\n\t\t\tm&#91;i]&#91;j]=0;\n\t\t\treturn 0;\n\t\t}\n\t\tif(m&#91;i]&#91;j]!=0)\n\t\t\treturn m&#91;i]&#91;j];\n\t\tint min=Integer.MAX_VALUE;\n\t\tfor(int k=i;k&lt;j;k++){\n\t\t\tint d=MatrixChain(p,m,s,i,k)+MatrixChain(p,m,s,k+1,j)+p&#91;i-1]*p&#91;k]*p&#91;j];\n\t\t\tif(d&lt;min){\n\t\t\t\tm&#91;i]&#91;j]=min=d;\n\t\t\t\ts&#91;i]&#91;j]=k;\n\t\t\t}\n\t\t}\n\t\treturn min;\n\t}\n\t\n\tprivate static void TraceBack(int i,int j,int&#91;]&#91;] s){\n\t\tif(i==j)\n\t\t\treturn;\n\t\tTraceBack(i,s&#91;i]&#91;j],s);\n\t\tTraceBack(s&#91;i]&#91;j]+1,j,s);\n\t\tSystem.out.println(\"A&#91;\"+i+\"]&#91;\"+s&#91;i]&#91;j]+\"] * \"+\"A&#91;\"+(s&#91;i]&#91;j]+1)+\"]&#91;\"+j+\"]\");\n\t}\n\t\n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tint&#91;]&#91;] m=new int&#91;100]&#91;100];\n\t\tint&#91;]&#91;] s=new int&#91;100]&#91;100];\n\t\tint&#91;] p=new int&#91;]{30,35,15,5,10,20,25};\n\t\tint len=p.length;\n\t\tSystem.out.println(\"Total : \"+MatrixChain(p,m,s,1,len-1));\n\t\tTraceBack(1,len-1,s);\n\t}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-380","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/380","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=380"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/380\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=380"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=380"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}