In some problems, the index The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different If we could add extra states to remember the result of the first run, then we could immediately return at the second run the states are the same. <\/p>\n\n\n\n We define the extra state as the total number of different songs we have played before index The first choice is not different: we play a new song. <\/p>\n\n\n\n The second choice is tricky: when we play an old song, how to ensure that there are at Least K unique songs after last time it got played? Look at the following graph. <\/p>\n\n\n\n We know the the most recent k plays must contain k unique songs, or any two among them will violate the rules. And there are j unique songs among The problem is regarding a 2D matrix but it is still a linear structure. It is not difficult to figure out that we need an extra state to store how many cuts we already have at Summary In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained. The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,55],"tags":[],"class_list":["post-1210","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-in-linear-structures"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1210","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=1210"}],"version-history":[{"count":6,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1210\/revisions"}],"predecessor-version":[{"id":1212,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1210\/revisions\/1212"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1210"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1210"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}i<\/code> is not enough to make subproblems alg[i] <\/code>independent to the previous sequences s[0,i-1]<\/code>. We need one or several extra states to make subproblem self-contained. <\/p>\n\n\n\ndfs<\/code> enter the same index i<\/code> at the linear sequence, but the later possibilities after i<\/code> are the same. <\/p>\n\n\n\nDetails <\/h2>\n\n\n\n
920. Number of Music Playlists<\/a><\/h4>\n\n\n\n
i<\/code>.<\/p>\n\n\n\nalg[i][j] = \n 1. (N - j) * alg[i + 1][j + 1]<\/code><\/pre>\n\n\n\n.....xxxx i\n ____\n k\n_________\n j <\/code><\/pre>\n\n\n\narr[0,i-1]<\/code>, which means all the (j-k)<\/code> could be chosen at index i<\/code>. So we have,<\/p>\n\n\n\nalg[i][j] = \n 1. (N - j) * alg[i + 1][j + 1]\n 2. (j - k) * alg[i + 1][j] if j >= k \n\/\/ alg[L][N] = 1;<\/code><\/pre>\n\n\n\nLC 1444. Number of Ways of Cutting a Pizza<\/a><\/h4>\n\n\n\n
alg[i, j]<\/code>.<\/p>\n\n\n\nalg[i][j][k] = sum {\n 1. alg[ii][j][k+1] if curr_pizza > 0 for ii in [i+1, m-1], curr_pizza = sum[i][j] - sum[ii][j]\n 2. alg[i][jj][k+1] if curr_pizza > 0 for jj in [j+1, n-1], curr_pizza = sum[i][j] - sum[i][jj]\n}\n\/\/ alg[i][j][K - 1] = sum[i][j] > 0 ? 1 : 0\n\nsum[i][j] = pizza[i][j] == 'A' +sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1]\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"