Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. <\/p>\n\n\n\n
There are N piles of stones arranged in a row. The i-th pile has stones[i] stones. A move consists of merging 2 consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these 2 piles. Find the minimum cost to merge all piles of stones into one pile.<\/p>\n\n\n\n
Think backwards. Consider the last pile in range An interesting variance of this problem is that any two stones can be merged. In this case, we can greedily choose smaller stones to merge together, which becomes a Huffman Code problem. <\/p>\n\n\n\n This problem involves another dimension and it also needs to be thought backwards. Consider the last pile in range Think backwards. Consider Think backwards. Consider Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…<\/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-782","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\/782","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=782"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/782\/revisions"}],"predecessor-version":[{"id":1165,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/782\/revisions\/1165"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=782"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=782"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}nums[i,...,j]<\/code> is formed by “Super Stone” nums[i,...,k]<\/code> and “Super Stone” nums[k + 1,...,j]<\/code>. Here “Super Stone” nums[i,...,k]<\/code> means these stones will form into a single stone. <\/p>\n\n\n\nalg[i][j]=min(alg[i][j],alg[i][k]+alg[k+1][j]+sum[i][j]), k in [i, j - 1]<\/code><\/pre>\n\n\n\nLC 1000. Minimum Cost to Merge Stones II<\/a> <\/h4>\n\n\n\n
nums[i,...,j]<\/code> is formed by K<\/code> piles of stones. nums[i,...,l]<\/code> forms one pile and nums[l + 1,...,j]<\/code> forms K-1<\/code> piles. <\/p>\n\n\n\nalg[i][j][k] (k >= 2) =\n min{ alg[i][l][1] + alg[l + 1][j][k - 1] for l in [i, ... j - 1]}\n\/\/ Note that is not min{ alg[i][l][1] + alg[l + 1][j][k - 1] + sum[i][j]}! Since forming k piles does not need to pay. \nalg[i][j][1] = alg[i][j][k] + sum[i][j]\n\n\/\/ alg[i][i][1] = 0\n\/\/ sum[i][j]: prefix_sum[j] - ((i - 1 >= 0) ? prefix_sum[i - 1] : 0)<\/code><\/pre>\n\n\n\nLC 1130. Minimum Cost Tree From Leaf Values<\/a><\/h4>\n\n\n\n
nums[k]<\/code> is the last number in range nums[i,...,j]<\/code>. nums[i,...,k]<\/code> forms the left subtree, and nums[k + 1,...,j]<\/code> forms the right subtree. <\/p>\n\n\n\nmax_num[i][j] = max(max_num[i + 1][j - 1], nums[i], nums[j])\n\nalg[i][j] = min {alg[i][k] + alg[k + 1][j] + max_num[i][k] * max_num[k + 1][j], for k in [i, ..., j - 1]}\n\n\/\/ alg[i][i] = 0\n\/\/ alg[i][i + 1] = nums[i] * nums[i + 1]<\/code><\/pre>\n\n\n\nLC 312.\u00a0Burst Balloons<\/a><\/h4>\n\n\n\n
nums[k]<\/code> is the last ballon in range nums[i+1,...,j-1]<\/code>. Thennums[i+1,...,k-1]<\/code> should be bursted out, and nums[k+1,...,j-1]<\/code> should also be bursted out. nums[i+1,...,k-1]<\/code> will be alg[i][k]<\/code>.<\/p>\n\n\n\n\/\/ pad nums => {1, nums[0], ..., nums[n - 1], 1}\nalg[i][j] = max { nums[i] * nums[j] * nums[k] + alg[i][k] + alg[k][j], for k in [i + 1, ..., j - 1]}\n\n\/\/ alg[i][i] = INT_MIN\n\/\/ alg[i][i + 1] = INT_MIN<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"