{"id":1092,"date":"2020-04-29T17:08:45","date_gmt":"2020-04-30T00:08:45","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1092"},"modified":"2020-04-29T17:09:39","modified_gmt":"2020-04-30T00:09:39","slug":"combination-permutation-dp-counting","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/29\/combination-permutation-dp-counting\/","title":{"rendered":"Combination &#038; Permutation &#038; DP Counting"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations. <\/p>\n\n\n\n<p>Some typical rules and corresponding solutions are listed below. <\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><strong>At most x same consecutive elements<\/strong>; the solution is to use a dimension to record the consecutive elements or handle them while transfer states<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">OJ<\/h2>\n\n\n\n\n<table id=\"tablepress-14\" class=\"tablepress tablepress-id-14\">\n<thead>\n<tr class=\"row-1\">\n\t<td class=\"column-1\"><\/td><th class=\"column-2\">Trick<\/th><th class=\"column-3\">Difficulty<\/th>\n<\/tr>\n<\/thead>\n<tbody class=\"row-striping row-hover\">\n<tr class=\"row-2\">\n\t<td class=\"column-1\"><a href=\"https:\/\/leetcode.com\/problems\/dice-roll-simulation\/\" target=\"_blank\" rel=\"noopener noreferrer\"> LC 1223. Dice Roll Simulation<\/a><\/td><td class=\"column-2\">DP Counting + Permutation + Consecutive Constraints<\/td><td class=\"column-3\">5-6 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<!-- #tablepress-14 from cache -->\n\n\n\n<h2 class=\"wp-block-heading\">Details<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/dice-roll-simulation\/\" target=\"_blank\">LC 1223. Dice Roll Simulation<\/a><\/h4>\n\n\n\n<p>We handle the consecutive constrains while transferring states. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ each i will start a new consecutive sequence with length 1 to rollMax[j]\n\/\/ starting a new sequence means j will differ from prev\nalg[i][prev] = sum {\n   alg[i + k][j] for k in [1, rollMax[j]] for j != prev &amp;&amp; j in [1, 6]\n}<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Summary A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations. Some typical rules and corresponding solutions are listed below. At most x same consecutive elements; the solution is to use a dimension to record the consecutive&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,60],"tags":[],"class_list":["post-1092","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-counting"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1092","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1092"}],"version-history":[{"count":2,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1092\/revisions"}],"predecessor-version":[{"id":1095,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1092\/revisions\/1095"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1092"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1092"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1092"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}