In this category, given a range 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 Given a range Summary In this category, given a range alg[i,j], we need to identify a middle point k and change the problem into alg[i,k] and alg[k+1, j]. Details LC 375. Guess Number Higher or Lower II Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually…<\/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],"tags":[],"class_list":["post-1162","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-in-intervals"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1162","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=1162"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1162\/revisions"}],"predecessor-version":[{"id":1175,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1162\/revisions\/1175"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}alg[i,j]<\/code>, we need to identify a middle point k<\/code> and change the problem into alg[i,k] and alg[k+1, j]<\/code>.<\/p>\n\n\n\nDetails<\/h2>\n\n\n\n
LC 375. Guess Number Higher or Lower II<\/a> <\/h4>\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\nLC 664. Strange Printer<\/a><\/h4>\n\n\n\n
alg[i,j]<\/code>, we could instantly print i<\/code> and reduce the problem to alg[i+1,j]<\/code>. Or we could hold i<\/code> and add it to k<\/code>, which means we print s[i,k]<\/code> all together with s[i]<\/code>, then the problem is reduced to alg[i + 1][k - 1]<\/code> and alg[k][j]<\/code>.<\/p>\n\n\n\nalg[i][j] \n 1. print i alone\n 1 + alg[i + 1][j] \n 2. i together with k i xxxx k xxx j\n alg[i + 1][k - 1] + alg[k][j] if s[i] == s[k] for k in [i + 1, j]\n\/\/ alg[i][i] = 1\n\/\/ alg[i][i+1] = (s[i] == s[i + 1]) ? 1 : 2<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"