{"id":92236,"date":"2020-05-15T20:16:49","date_gmt":"2020-05-15T12:16:49","guid":{"rendered":"http:\/\/4563.org\/?p=92236"},"modified":"2020-05-15T20:16:49","modified_gmt":"2020-05-15T12:16:49","slug":"%e8%af%b7%e9%97%ae%e8%bf%99%e7%a7%8d%e9%a2%98%e7%9b%ae%e6%80%8e%e4%b9%88-dp-%e5%95%8a%ef%bc%9f","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=92236","title":{"rendered":"\u8bf7\u95ee\u8fd9\u79cd\u9898\u76ee\u600e\u4e48 dp \u554a\uff1f"},"content":{"rendered":"<div>\n<div>\n<div>\n<h1>                  \u8bf7\u95ee\u8fd9\u79cd\u9898\u76ee\u600e\u4e48 dp \u554a\uff1f               <\/h1>\n<p> <\/p>\n<div>\n<div> <span>\u8cc7\u6df1\u5927\u4f6c : Newyorkcity <\/span>  <span><i><\/i> 27<\/span> <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n<div isfirst=\"1\"> <\/p>\n<p>https:\/\/leetcode-cn.com\/problems\/freedom-trail\/<\/p>\n<p>\u522b\u7684\u4e0d\u8bf4\uff0c\u5c31\u6bd4\u5982\u5728\u524d\u5f80 key[i] \u65f6\uff0c\u9006\u65f6\u9488\u548c\u987a\u65f6\u9488\u6ce2\u52a8\u4ee5\u5230\u8fbe\u7684\u4e00\u4e2a\u6700\u8fd1\u4f4d\u7f6e\u7684\u82b1\u8d39\u662f\u4e00\u6837\u7684\uff0cdp \u5982\u4f55\u8868\u8fbe\u8fd9\u4ef6\u4e8b\uff1f<\/p>\n<p>dfs \u7528\u8fc7\u4e86\uff0c\u8d85\u65f6\u3002\u3002\u3002<\/p>\n<pre><code>import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set;  public class Solution {      private String rring;     private String kkey;     private Map&lt;Character, Set&lt;Integer&gt;&gt; ringMap;     private int ans = Integer.MAX_VALUE;      public int findRotateSteps(String ring, String key) {         rring = ring;         kkey = key;         ringMap = new HashMap&lt;&gt;();         for (int i = 0; i &lt; ring.length(); i++) {             char c = ring.charAt(i);             Set&lt;Integer&gt; set = ringMap.getOrDefault(c, new HashSet&lt;Integer&gt;());             set.add(i);             ringMap.put(c, set);         }         dfs(0, 0, 0);         return ans;     }      public void dfs(int keyIdx, int nowIdx, int stepCounter) {         if (keyIdx == kkey.length()) {             ans = Math.min(ans, stepCounter);             return;         }         Character ch = kkey.charAt(keyIdx);         for (Integer nextIdx : ringMap.get(ch)) {             dfs(keyIdx + 1, nextIdx, stepCounter + 1 + distanceCounter(nowIdx,                     nextIdx));         }      }      public int distanceCounter(int nowIdx, int nextIdx) {         int a = Math.abs(nextIdx - nowIdx);         int b = rring.length() - a;         return Math.min(a, b);     } } <\/code><\/pre>\n<p>\u8c22\u8c22<\/p>\n<\/p><\/div>\n<div> <b>\u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (<span>0<\/span>)        <\/div>\n<div> <\/div>\n<\/p><\/div>\n<\/p><\/div>\n<ul>\n<li>\n","protected":false},"excerpt":{"rendered":"<p>\u8bf7\u95ee\u8fd9\u79cd\u9898\u76ee\u600e\u4e48 dp \u554a\uff1f \u8cc7\u6df1&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/92236"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=92236"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/92236\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=92236"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=92236"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=92236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}