{"id":963,"date":"2020-04-12T10:13:45","date_gmt":"2020-04-12T17:13:45","guid":{"rendered":"http:\/\/209.126.2.187\/?p=963"},"modified":"2020-05-28T20:30:15","modified_gmt":"2020-05-29T03:30:15","slug":"hard-to-detect-dp","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/12\/hard-to-detect-dp\/","title":{"rendered":"Hard-to-Detect DP"},"content":{"rendered":"\n

Summary <\/h2>\n\n\n\n

In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 1049. Last Stone Weight II <\/a><\/td>DP in Linear Structures (NP)<\/td>5 points<\/td>\n<\/tr>\n
LC 375. Guess Number Higher or Lower II <\/a><\/td>DP in Intervals<\/td>6-7 points<\/td>\n<\/tr>\n
LC 1316. Distinct Echo Substrings<\/a><\/td>Rolling Hash + string_view or DP in Linear Structure + string_view<\/td>6 points<\/td>\n<\/tr>\n
LC 338. Counting Bits<\/a><\/td>Bit Manipulation + DP<\/td>5 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

LC 1049. Last Stone Weight II<\/a><\/h4>\n\n\n\n

Think of it in this way: we divide the numbers into two groups, and calculate the minimum difference between the sum of the groups. <\/p>\n\n\n\n

alg[i][prev_sum] = \n    1. alg[i + 1][prev_sum + stones[i]]\n    2. alg[i + 1][prev_sum]\n\/\/ alg[n][prev_sum] = abs(sum - prev_sum - prev_sum)<\/code><\/pre>\n\n\n\n
LC 375. Guess Number Higher or Lower II<\/a> <\/h4>\n\n\n\n
Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually we do not know which number to guess is the best, which indicates DP. After we guess one, the actual number might be larger or might be smaller. Here comes the MinMax.<\/p>\n\n\n\n
alg[i][j] = min{ k + max(alg[i][k - 1], alg[k + 1][j]), for k in [i+1,...,j-1]}\n\/\/  alg[i][i] = 0, no need to pay for a single number\n\/\/  alg[i][i + 1] = i, pay as less as possible<\/code><\/pre>\n\n\n\n
LC 1316. Distinct Echo Substrings<\/a><\/h4>\n\n\n\n
It is not hard to get the rolling hash solution. Actually DP is a better way because it has no hash collision. <\/p>\n\n\n\n
alg[i][j]\n  1. s[i] == s[j]: 1 + alg[i + 1][j + 1]\n  2. s[i] != s[j]: 0\n\n\/\/ alg[i][j] has a echo string iif alg[i][j] >= (j - i)\n\/\/ since \"aaaaaa\" has a[0][2]=4<\/code><\/pre>\n\n\n\n
LC 338. Counting Bits<\/a><\/h4>\n\n\n\n
There are several ways to connect the current number to a previous number. <\/p>\n\n\n\n
Last Set Bit<\/strong> (rightmost set bit): alg[i]=alg[i&(i-1)]+1<\/code> . The trick i&(i-1)<\/code>reset the last set bit. <\/p>\n\n\n\n
Least Significant Bit<\/strong> (rightmost bit): alg[i]=alg[i>>1]+(i&1)<\/code>.<\/p>\n\n\n\n
First Set Bit<\/strong> (leftmost set bit): alg[i]=alg[i-(1<<num_bit)]+1<\/code>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,50,55],"tags":[],"class_list":["post-963","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-in-intervals","category-dp-in-linear-structures"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/963","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=963"}],"version-history":[{"count":7,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/963\/revisions"}],"predecessor-version":[{"id":1270,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/963\/revisions\/1270"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}