{"id":4257,"date":"2018-11-04T07:58:59","date_gmt":"2018-11-04T15:58:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4257"},"modified":"2018-11-07T20:46:04","modified_gmt":"2018-11-08T04:46:04","slug":"leetcode-935-knight-dialer","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-935-knight-dialer\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 935. Knight Dialer"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 935. Knight Dialer - \u5237\u9898\u627e\u5de5\u4f5c EP229\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/HTnIFivp0aw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/knight-dialer\/description\/\">https:\/\/leetcode.com\/problems\/knight-dialer\/description\/<\/a><\/p>\n<p>A chess knight can move as indicated in the chess diagram below:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/12\/knight.png\" alt=\"\" \/>\u00a0.\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0<img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2018\/10\/30\/keypad.png\" alt=\"\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes\u00a0<code>N-1<\/code>\u00a0hops.\u00a0 Each hop must be from one key to another numbered key.<\/p>\n<p>Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing\u00a0<code>N<\/code>\u00a0digits total.<\/p>\n<p>How many distinct numbers can you dial in this manner?<\/p>\n<p>Since the answer may be large,\u00a0<strong>output the answer\u00a0modulo\u00a0<code>10^9 + 7<\/code><\/strong>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-1-1\">1<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">10<\/span>\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-2-1\">2<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">20<\/span>\r\n<\/pre>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong><span id=\"example-input-3-1\">3<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-3\">46<\/span>\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>1 &lt;= N &lt;= 5000<\/code><\/li>\n<\/ul>\n<h1><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4265\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/11\/935-ep229.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/11\/935-ep229.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/11\/935-ep229-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/11\/935-ep229-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/h1>\n<h1><strong>Solution: DP<\/strong><\/h1>\n<h2>V1<\/h2>\n<p>Similar to\u00a0<a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/688-knight-probability-in-chessboard\/\">\u82b1\u82b1\u9171 688. Knight Probability in Chessboard<\/a><\/p>\n<p>We can define dp[k][i][j] as # of ways to dial and the last key is (j, i) after k steps<\/p>\n<p>Note: dp[*][3][0], dp[*][3][2] are always zero for all the steps.<\/p>\n<p>Init: dp[0][i][j] = 1<\/p>\n<p>Transition: dp[k][i][j] = sum(dp[k &#8211; 1][i + dy][j + dx]) 8 ways of move from last step.<\/p>\n<p>ans = sum(dp[k])<\/p>\n<p>Time complexity: O(kmn) or O(k * 12 * 8) = O(k)<\/p>\n<p>Space complexity: O(kmn) -&gt; O(mn) or O(12*8) = O(1)<\/p>\n<h2>V2<\/h2>\n<p>define dp[k][i] as # of ways to dial and the last key is i after k steps<\/p>\n<p>init: dp[0][0:10] = 1<\/p>\n<p>transition: dp[k][i] = sum(dp[k-1][j]) that j can move to i<\/p>\n<p>ans: sum(dp[k])<\/p>\n<p>Time complexity: O(k * 10) = O(k)<\/p>\n<p>Space complexity: O(k * 10) -&gt; O(10) = O(1)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++ V1<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua, 96 ms\r\nclass Solution {\r\npublic:\r\n  int knightDialer(int N) {\r\n    constexpr int kMod = 1e9 + 7;\r\n    int dirs[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};\r\n    vector&lt;vector&lt;int&gt;&gt; dp(4, vector&lt;int&gt;(3, 1));\r\n    dp[3][0] = dp[3][2] = 0;    \r\n    for (int k = 1; k &lt; N; ++k) {\r\n      vector&lt;vector&lt;int&gt;&gt; tmp(4, vector&lt;int&gt;(3));\r\n      for (int i = 0; i &lt; 4; ++i)\r\n        for (int j = 0; j &lt; 3; ++j) {\r\n          if (i == 3 &amp;&amp; j != 1) continue;\r\n          for (int d = 0; d &lt; 8; ++d) {           \r\n            int tx = j + dirs[d][0];\r\n            int ty = i + dirs[d][1];\r\n            if (tx &lt; 0 || ty &lt; 0 || tx &gt;= 3 || ty &gt;= 4) continue;\r\n            tmp[i][j] = (tmp[i][j] + dp[ty][tx]) % kMod;\r\n          }          \r\n        }\r\n      dp.swap(tmp);\r\n    }\r\n    int ans = 0;\r\n    for (int i = 0; i &lt; 4; ++i)\r\n      for (int j = 0; j &lt; 3; ++j)\r\n        ans = (ans + dp[i][j]) % kMod;\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ V2<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua, 24 ms\r\npublic:\r\n  int knightDialer(int N) {\r\n    constexpr int kMod = 1e9 + 7;\r\n    vector&lt;vector&lt;int&gt;&gt; moves{{4,6},{8,6},{7,9},{4,8},{3,9,0},{},{1,7,0},{2,6},{1,3},{2,4}};\r\n    vector&lt;int&gt; dp(10, 1);\r\n    for (int k = 1; k &lt; N; ++k) {\r\n      vector&lt;int&gt; tmp(10);\r\n      for (int i = 0; i &lt; 10; ++i)\r\n        for (int nxt : moves[i])\r\n          tmp[nxt] = (tmp[nxt] + dp[i]) % kMod;        \r\n      dp.swap(tmp);\r\n    }\r\n    int ans = 0;\r\n    for (int i = 0; i &lt; 10; ++i)\r\n      ans = (ans + dp[i]) % kMod;\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problem<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/688-knight-probability-in-chessboard\/\">\u82b1\u82b1\u9171 688. Knight Probability in Chessboard<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-576-out-of-boundary-paths\/\">\u82b1\u82b1\u9171 LeetCode 576. Out of Boundary Paths<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem https:\/\/leetcode.com\/problems\/knight-dialer\/description\/ A chess knight can move as indicated in the chess diagram below: \u00a0.\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 &nbsp; This time, we place&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[119,18,118],"class_list":["post-4257","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-chess","tag-dp","tag-knight","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4257"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4257\/revisions"}],"predecessor-version":[{"id":4266,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4257\/revisions\/4266"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}