“`” \u53c2\u8003\u56de\u7b54\uff1a<\/p>\n
\u5047\u8bbe\u67091 \u5143\uff0c3 \u5143\uff0c5 \u5143\u7684\u786c\u5e01\uff0c\u5047\u8bbe\u4e00\u4e2a\u51fd\u6570 d(i) \u6765\u8868\u793a\u9700\u8981\u51d1\u51fa i \u7684\u603b\u4ef7\u503c\u9700\u8981\u7684\u6700\u5c11\u786c\u5e01\u6570\u91cf\u3002<\/p>\n
\u5f53i = 0 \u65f6\uff0c d(0) = 0\u3002\u4e0d\u9700\u8981\u51d1\u96f6\u94b1\uff0c\u5f53\u7136\u4e5f\u4e0d\u9700\u8981\u4efb\u4f55\u786c\u5e01\u4e86\u3002<\/p>\n
\u5f53i = 1 \u65f6\uff0c\u56e0\u4e3a\u6709 1 \u5143\u7684\u786c\u5e01\uff0c\u6240\u4ee5\u76f4\u63a5\u5728\u7b2c 1 \u6b65\u7684\u57fa\u7840\u4e0a\uff0c\u52a0\u4e0a 1 \u4e2a 1 \u5143\u786c\u5e01\uff0c\u5f97\u51fa d(1) = 1\u3002<\/p>\n
\u5f53i = 2 \u65f6\uff0c\u56e0\u4e3a\u5e76\u6ca1\u6709 2 \u5143\u7684\u786c\u5e01\uff0c\u6240\u4ee5\u53ea\u80fd\u62ff 1 \u5143\u7684\u786c\u5e01\u6765\u51d1\u3002\u5728\u7b2c 2 \u6b65\u7684\u57fa\u7840\u4e0a\uff0c\u52a0\u4e0a 1 \u4e2a 1 \u5143\u786c\u5e01\uff0c\u5f97\u51fa d(2) = 2\u3002<\/p>\n
\u5f53i = 3 \u65f6\uff0c\u53ef\u4ee5\u5728\u7b2c 3 \u6b65\u7684\u57fa\u7840\u4e0a\u52a0\u4e0a 1 \u4e2a 1 \u5143\u786c\u5e01\uff0c\u5f97\u5230 3 \u8fd9\u4e2a\u7ed3\u679c\u3002\u4f46\u5176\u5b9e\u6709 3 \u5143\u786c\u5e01\uff0c\u6240\u4ee5\u8fd9\u4e00\u6b65\u7684\u6700\u4f18\u7ed3\u679c\u4e0d\u662f\u5efa\u7acb\u5728\u7b2c 3 \u6b65\u7684\u7ed3\u679c\u4e0a\u5f97\u6765\u7684\uff0c\u800c\u662f\u5e94\u8be5\u5efa\u7acb\u5728\u7b2c 1 \u6b65\u4e0a\uff0c\u52a0\u4e0a 1 \u4e2a 3 \u5143\u786c\u5e01\uff0c\u5f97\u5230 d(3) = 1\u3002<\/p>\n
\u9664\u4e86\u7b2c1 \u6b65\u8fd9\u4e2a\u770b\u4f3c\u57fa\u672c\u7684\u516c\u7406\u5916\uff0c\u5176\u4ed6\u5f80\u540e\u7684\u7ed3\u679c\u90fd\u662f\u5efa\u7acb\u5728\u5b83\u4e4b\u524d\u5f97\u5230\u7684\u67d0\u4e00\u6b65\u7684\u6700\u4f18\u89e3\u4e0a\uff0c\u52a0\u4e0a 1 \u4e2a\u786c\u5e01\u5f97\u5230\u3002\u5f97\u51fa\uff1a<\/p>\n
d(i) = d(j) + 1<\/p>\n
\u8fd9\u91ccj < i\u3002\u901a\u4fd7\u5730\u8bb2\uff0c\u6211\u4eec\u9700\u8981\u51d1\u51fa i \u5143\uff0c\u5c31\u5728\u51d1\u51fa j \u7684\u7ed3\u679c\u4e0a\u518d\u52a0\u4e0a\u67d0\u4e00\u4e2a\u786c\u5e01\u5c31\u884c\u4e86\u3002<\/p>\n
\u90a3\u8fd9\u91cc\u6211\u4eec\u52a0\u4e0a\u7684\u662f\u54ea\u4e2a\u786c\u5e01\u5462\u3002\u55ef\uff0c\u5176\u5b9e\u5f88\u7b80\u5355\uff0c\u628a\u6bcf\u4e2a\u786c\u5e01\u8bd5\u4e00\u4e0b\u5c31\u884c\u4e86\uff1a<\/p>\n
\u2022 \u5047\u8bbe\u6700\u540e\u52a0\u4e0a\u7684\u662f1 \u5143\u786c\u5e01\uff0c\u90a3 d(i) = d(j) + 1 = d(i – 1) + 1\u3002<\/p>\n
\u2022 \u5047\u8bbe\u6700\u540e\u52a0\u4e0a\u7684\u662f3 \u5143\u786c\u5e01\uff0c\u90a3 d(i) = d(j) + 1 = d(i – 3) + 1\u3002<\/p>\n
\u2022 \u5047\u8bbe\u6700\u540e\u52a0\u4e0a\u7684\u662f5 \u5143\u786c\u5e01\uff0c\u90a3 d(i) = d(j) + 1 = d(i – 5) + 1\u3002<\/p>\n
\u6211\u4eec\u5206\u522b\u8ba1\u7b97\u51fad(i – 1) + 1\uff0cd(i – 3) + 1\uff0cd(i – 5) + 1 \u7684\u503c\uff0c\u53d6\u5176\u4e2d\u7684\u6700\u5c0f\u503c\uff0c\u5373\u4e3a\u6700\u4f18\u89e3\uff0c\u4e5f\u5c31\u662f d(i)\u3002<\/p>\n
\u6700\u540e\u516c\u5f0f\uff1a<\/p>\n
\u00a0<\/p>\n
\u4ee3\u7801\u793a\u4f8b\uff1a<\/p>\n
public class CoinProblemBasicTest {<\/p>\n
private int[] d; \/\/ \u50a8\u5b58\u7ed3\u679c<\/p>\n
private int[] coins = {1, 3, 5}; \/\/ \u786c\u5e01\u79cd\u7c7b<\/p>\n
<pre><code>private void d_func(int i, int num) {
\nif (i == 0) {
\nd[i] = 0;
\nd_func(i + 1, num);
\n}
\nelse {
\nint min = 9999999;
\nfor (int coin : coins) {
\nif (i >= coin && d[i – coin] + 1 < min) {
\nmin = d[i – coin] + 1;
\n}
\n}
\nd[i] = min;
\nif (i < num) {
\nd_func(i + 1, num);
\n}
\n}
\n}
\npublic void test() throws Exception {
\n<\/code><\/pre><\/p>\n
int sum = 11; \/\/ \u9700\u8981\u51d1 11 \u5143<\/p>\n
d = new int[sum + 1]; \/\/ \u521d\u59cb\u5316\u6570\u7ec4<\/p>\n
d_func(0, sum); \/\/ \u8ba1\u7b97\u9700\u8981\u51d1\u51fa 0 \uff5e sum \u5143\u9700\u8981\u7684\u786c\u5e01\u6570\u91cf<\/p>\n
for (int i = 0; i <= sum; i++) {<\/p>\n
System.out.println(""\u51d1\u9f50 "" + i + "" \u5143\u9700\u8981 "" + d[i] + "" \u4e2a\u786c\u5e01"");<\/p>\n
}<\/p>\n
}<\/p>\n
}<\/p>\n
<pre><code> "“`
\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
“`” \u53c2\u8003\u56de\u7b54\uff1a \u5047\u8bbe\u67091 \u5143\uff0c3 \u5143\uff0c5 \u5143\u7684\u786c\u5e01\uff0c\u5047\u8bbe\u4e00\u4e2a\u51fd\u6570 d(i) \u6765\u8868\u793a […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-38376","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38376","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=38376"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38376\/revisions"}],"predecessor-version":[{"id":38377,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/38376\/revisions\/38377"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=38376"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=38376"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=38376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}