{"id":527,"date":"2021-05-23T12:12:40","date_gmt":"2021-05-23T04:12:40","guid":{"rendered":"http:\/\/120.55.184.7\/?p=527"},"modified":"2025-04-15T18:15:06","modified_gmt":"2025-04-15T10:15:06","slug":"%e6%95%b0%e4%bd%8ddp","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=527","title":{"rendered":"\u6570\u4f4dDP"},"content":{"rendered":"\n<p>\u6570\u4f4dDP\u662f\u4e00\u79cd\u7528\u4e8e\u89e3\u51b3\u4e0e\u6570\u5b57\u6570\u4f4d\u76f8\u5173\u95ee\u9898\u7684\u52a8\u6001\u89c4\u5212\u6280\u672f\uff0c\u7279\u522b\u9002\u5408\u5904\u7406\u5927\u8303\u56f4\u5185\u7684\u6570\u5b57\u7edf\u8ba1\u95ee\u9898\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e00\u3001\u6838\u5fc3\u6982\u5ff5<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u6570\u4f4d\u5b9a\u4e49<\/strong>\uff1a\u5c06\u6570\u5b57\u6309\u4f4d\u5206\u89e3\uff08\u5982\u5341\u8fdb\u5236\u7684\u4e2a\u3001\u5341\u3001\u767e\u4f4d\uff09\uff0c\u6bcf\u4f4d\u53d6\u503c\u8303\u56f4\u4e3a0\u52309\uff08\u6216\u5176\u4ed6\u8fdb\u5236\u5bf9\u5e94\u8303\u56f4\uff09\u3002<\/li>\n\n\n\n<li><strong>\u9002\u7528\u573a\u666f<\/strong>\uff1a<br>\u2022 \u7edf\u8ba1\u533a\u95f4 [L, R] \u5185\u6ee1\u8db3\u7279\u5b9a\u6761\u4ef6\u7684\u6570\u5b57\u4e2a\u6570\uff08\u5982\u4e0d\u542b\u6570\u5b574\u6216\u8fde\u7eed62\uff09<br>\u2022 \u6570\u636e\u8303\u56f4\u6781\u5927\uff08\u598210<sup>18<\/sup>\uff09\uff0c\u65e0\u6cd5\u66b4\u529b\u679a\u4e3e\u3002<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e8c\u3001\u7b97\u6cd5\u601d\u60f3<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u5206\u6cbb\u601d\u60f3<\/strong>\uff1a\u5c06\u6570\u5b57\u4ece\u9ad8\u4f4d\u5230\u4f4e\u4f4d\u9010\u4f4d\u5904\u7406\uff0c\u901a\u8fc7\u72b6\u6001\u8f6c\u79fb\u8bb0\u5f55\u5b50\u95ee\u9898\u89e3\u3002<\/li>\n\n\n\n<li><strong>\u72b6\u6001\u8bbe\u8ba1<\/strong>\uff1a<br>\u2022 <code>pos<\/code>\uff1a\u5f53\u524d\u5904\u7406\u5230\u7684\u6570\u4f4d\u4f4d\u7f6e<br>\u2022 <code>limit<\/code>\uff1a\u5f53\u524d\u4f4d\u662f\u5426\u53d7\u4e0a\u9650\u7ea6\u675f\uff08\u5982\u6570\u5b57123\u7684\u5341\u4f4d\u82e5\u4e3a2\uff0c\u4e2a\u4f4d\u6700\u591a\u53d63\uff09<br>\u2022 <code>lead<\/code>\uff1a\u662f\u5426\u6709\u524d\u5bfc\u96f6\uff08\u5f71\u54cd\u6570\u5b57\u6709\u6548\u6027\u5224\u65ad\uff09<br>\u2022 \u5176\u4ed6\u81ea\u5b9a\u4e49\u72b6\u6001\uff08\u5982\u524d\u4e00\u4f4d\u6570\u5b57<code>pre<\/code>\u3001\u6570\u5b57\u548c<code>sum<\/code>\u7b49\uff09<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e09\u3001\u5b9e\u73b0\u6a21\u677f\uff08C++\uff09<\/h3>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\ntypedef long long ll;\nint a&#x5B;20]; \/\/ \u5b58\u50a8\u6570\u5b57\u5404\u4f4d\nll dp&#x5B;20]&#x5B;state]; \/\/ \u72b6\u6001\u6570\u7ec4\uff0cstate\u6839\u636e\u95ee\u9898\u5b9a\u4e49\n\nll dfs(int pos, int state, bool lead, bool limit) {\n    if (pos == -1) return 1; \/\/ \u9012\u5f52\u7ec8\u6b62\u6761\u4ef6\uff0c\u6839\u636e\u95ee\u9898\u8c03\u6574\u8fd4\u56de\u503c\n    if (!limit &amp;&amp; !lead &amp;&amp; dp&#x5B;pos]&#x5B;state] != -1) \n        return dp&#x5B;pos]&#x5B;state]; \/\/ \u8bb0\u5fc6\u5316\n\n    int up = limit ? a&#x5B;pos] : 9;\n    ll res = 0;\n    for (int i = 0; i &lt;= up; ++i) {\n        if (\u95ee\u9898\u7279\u5b9a\u6761\u4ef6) continue; \/\/ \u5982i==4\u8df3\u8fc7\n        res += dfs(pos-1, \u65b0\u72b6\u6001, lead &amp;&amp; (i==0), limit &amp;&amp; (i==up));\n    }\n    if (!limit &amp;&amp; !lead) dp&#x5B;pos]&#x5B;state] = res; \/\/ \u8bb0\u5f55\u975e\u53d7\u9650\u72b6\u6001\n    return res;\n}\n\nll solve(ll x) {\n    int pos = 0;\n    while (x) { a&#x5B;pos++] = x % 10; x \/= 10; }\n    memset(dp, -1, sizeof(dp));\n    return dfs(pos-1, \u521d\u59cb\u72b6\u6001, true, true);\n}\n\/\/ \u8c03\u7528\uff1asolve(R) - solve(L-1)\n<\/pre><\/div>\n\n\n<h4 class=\"wp-block-heading\"><\/h4>\n\n\n\n<h3 class=\"wp-block-heading\">\u56db\u3001\u7ecf\u5178\u4f8b\u9898<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u4e0d\u898162<\/strong>\uff08HDU 2089\uff09\uff1a<br>\u2022 \u72b6\u6001\u9700\u8bb0\u5f55\u524d\u4e00\u4f4d\u662f\u5426\u4e3a<code>6<\/code>\uff0c\u5f53\u524d\u4f4d\u4e0d\u80fd\u4e3a<code>2<\/code>\u3002<\/li>\n\n\n\n<li><strong>\u6570\u5b571\u7684\u4e2a\u6570<\/strong>\uff08LeetCode 233\uff09\uff1a<br>\u2022 \u7edf\u8ba1\u6bcf\u4f4d\u51fa\u73b0<code>1<\/code>\u7684\u6b21\u6570\uff0c\u72b6\u6001\u8bb0\u5f55\u7d2f\u8ba1\u7684<code>1<\/code>\u7684\u6570\u76ee\u3002<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e94\u3001\u4f18\u5316\u6280\u5de7<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u4e8c\u8fdb\u5236\u62c6\u5206<\/strong>\uff1a\u5904\u7406\u591a\u91cd\u7ea6\u675f\u65f6\u5408\u5e76\u72b6\u6001\u3002<\/li>\n\n\n\n<li><strong>\u72b6\u6001\u538b\u7f29<\/strong>\uff1a\u7528\u4f4d\u8fd0\u7b97\u8bb0\u5f55\u6570\u5b57\u4f7f\u7528\u60c5\u51b5\uff08\u5982<code>state<\/code>\u8868\u793a\u6570\u5b570-9\u662f\u5426\u51fa\u73b0\u8fc7\uff09\u3002<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">\u516d\u3001\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u65f6\u95f4<\/strong>\uff1aO(log<sub> 10<\/sub><sup>N<\/sup> S)\uff0cS\u4e3a\u72b6\u6001\u6570<\/li>\n\n\n\n<li><strong>\u7a7a\u95f4<\/strong>\uff1aO(log<sub> 10<\/sub><sup>N<\/sup> S) <\/li>\n<\/ul>\n\n\n\n<p>\u6570\u4f4dDP\u901a\u8fc7\u6570\u4f4d\u5206\u89e3\u548c\u72b6\u6001\u590d\u7528\uff0c\u5c06\u6307\u6570\u7ea7\u95ee\u9898\u8f6c\u5316\u4e3a\u591a\u9879\u5f0f\u590d\u6742\u5ea6\uff0c\u662f\u5904\u7406\u5927\u6570\u7edf\u8ba1\u95ee\u9898\u7684\u5229\u5668\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6570\u4f4dDP\u662f\u4e00\u79cd\u7528\u4e8e\u89e3\u51b3\u4e0e\u6570\u5b57\u6570\u4f4d\u76f8\u5173\u95ee\u9898\u7684\u52a8\u6001\u89c4\u5212\u6280\u672f\uff0c\u7279\u522b\u9002\u5408\u5904\u7406\u5927\u8303\u56f4\u5185\u7684\u6570\u5b57\u7edf\u8ba1\u95ee\u9898\u3002 \u4e00\u3001\u6838\u5fc3\u6982\u5ff5 \u4e8c [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[120],"class_list":["post-527","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-dp"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/527","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=527"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/527\/revisions"}],"predecessor-version":[{"id":531,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/527\/revisions\/531"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=527"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=527"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=527"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}