Details<\/h2>\n\n\n\nLC 1027. Longest Arithmetic Sequence<\/a><\/h4>\n\n\n\nIt is not difficult to get the following O(n^2logn)<\/code> solution. <\/p>\n\n\n\nalg[i][j] = \n alg[j][pos], let num=2*nums[j]-nums[i] in pos = lower_bound(num_to_pos[num], j + 1)<\/code><\/pre>\n\n\n\nHowever, if we adopt the following state definition, the complexity reduces to O(n^2)<\/code>. A tricky part is that the difference seems to be of O(n^2)<\/code> complexity for an array. But here, the difference for each i will only be O(n)<\/code> because of j > i<\/code>.<\/p>\n\n\n\n\/\/ vector<unordered_map>\nalg[i][diff]: sequence starting at i with different==diff\n\nlet diff=nums[j]-nums[i] in \n alg[i][diff] = max {\n diff in alg[j] ? alg[j][diff] + 1 : 2; for j in [i+1, n-1]}<\/code><\/pre>\n\n\n\nLC 446. Arithmetic Slices II – Subsequence<\/a><\/h4>\n\n\n\nIt is not difficult to get the following O(n^3)<\/code> solution.<\/p>\n\n\n\nalg[i][j] = \n sum{ alg[j][k] == 0 ? 1 : alg[j][k] + 1 if nums[k] == 2 * nums[j] - nums[i] for k in [j+1, n-1] }\n\/\/ alg[j][k] + 1 because {nums[i] : sequence[j][k]} + {nums[i], nums[j], nums[k]}<\/code><\/pre>\n\n\n\nHowever, if we use the same arithmetic difference technique, we can reduce the complexity to O(n^2)<\/code>. An annoying thing here is that we only count subsequences of length >= 3<\/code>. We could use two tables to store subsequences of different lengths. <\/p>\n\n\n\n \/\/ sequence length > 2 \nalg[i][diff] = let diff = alg[j] - alg[i] in \n sum{ {diff in alg[j] ? alg[j][diff] : 0} + {diff in alg2[j] ? alg2[j][diff] : 0} for j in [i + 1, n - 1]}\n result += sum {alg[i].vals}\n \n\/\/ sequence length == 2\nalg2[i][diff] = let diff = alg[j] - alg[i] in \n alg2[i][diff]++ for j in [i + 1, n - 1]<\/code><\/pre>\n\n\n\nLC 1187. Make Array Strictly Increasing<\/a><\/h4>\n\n\n\nIt is not difficult to get the following O(mnlog(n))<\/code> solution.<\/p>\n\n\n\n\/\/ prev is in arr1[i - 1]::arr2\nalg[i][prev] = \n 1. if arr1[i] > prev\n 1) alg[i + 1][arr1[i]] \n \/\/ greadily choose the smallest larger one\n 2) 1 + alg[i + 1][j], j = upper_bound(arr2, prev); \n 2. if arr1[i] <= prev\n 1) 1 + alg[i + 1][j], j = upper_bound(arr2, prev); <\/code><\/pre>\n\n\n\nHowever, since prev<\/code> is always in arr1[i - 1]::arr2<\/code>, we could solve the problem in O(mn)<\/code> by enumerating the index of prev<\/code>. The advantage of using an index is that the next greater element is index+1<\/code>.<\/p>\n\n\n\n\/\/ starting at i, previous is arr2[j], if j == n, it means it is arr1[i - 1]\nalg[i][j] = \n 1. if arr1[i] > arr2[j] && j in [0, n - 2] \n 1) alg[i + 1][n]\n 2) 1 + alg[i + 1][j + 1]\n 2. if arr1[i] <= arr2[j] && j in [0, n - 2] \n 1) 1 + alg[i + 1][j + 1]\n 3. if arr1[i] > arr1[i - 1] && j == n\n 1) alg[i + 1][n] \n 2) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()\n 4. if arr[i] <= arr1[i - 1] && j == n\n 1) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()\n 5. if arr1[i] > arr2[j] && j == n - 1\n 1) alg[i + 1][n]\n 6. othercases will be -1<\/code><\/pre>\n\n\n\nLC 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons<\/a><\/h4>\n\n\n\nIt is not difficult to get the O(nm^2K)<\/code> solution. <\/p>\n\n\n\nalg[i][k][prev_max] = sum {\n 1. prev_max * alg[i + 1][k][prev_max]\n 2. alg[i + 1][k + 1][j] for j in [prev_max + 1, m]\n\n\/\/ alg[n][k][j] = 1 for j in [1, m]<\/code><\/pre>\n\n\n\nHowever, as we could see, the nested loop which enumerates the next prev_max<\/code> could be achieved by the prefix sum technique. To make implementation easier, I use another table to store prefix sum, which reduces the complexity to O(nmK)<\/code>.<\/p>\n\n\n\nalg[i][k][prev_max] = sum {\n 1. prev_max * alg[i + 1][k][prev_max]\n 2. alg2[i + 1][k + 1][prev_max+1] == sum {alg[i + 1][k + 1][j] for j in [prev_max + 1, m]}\n\n\/\/ alg[n][k][j] = 1 for j in [1, m]\n \n\/\/ alg2[i][k][m] = alg[i][k][m]\nalg2[i][k][j] = alg[i][k][j] + alg2[i][k][j + 1]<\/code><\/pre>\n\n\n\nLC 514. Freedom Trail<\/a><\/h4>\n\n\n\nIt is not difficult to get the O(nm^2)<\/code> solution.<\/p>\n\n\n\n\/\/ ring m, key n\n\/\/ ch_to_index is for ring\nalg[j][i]\n = cost(i, k) + alg[j + 1][k] for k in ch_to_index[key[j]]]<\/code><\/pre>\n\n\n\nActually, given any key[j]<\/code> and the current position i<\/code> at ring, we could greedily choose two same characters in ring: the nearest right and the nearest left. We could preprocess this in O(26mlogm)<\/code> time. Then the time complexity reduces to O(nm)<\/code>. <\/p>\n\n\n\nalg[j][i]\n = min(cost(i, left) + alg[j + 1][left], cost(i, right) + alg[j + 1][right])<\/code><\/pre>\n\n\n\nLC 1434. Number of Ways to Wear Different Hats to Each Other<\/a><\/h4>\n\n\n\nIt is not difficult to get the ![\"O(n_{people}\times n_{hat}\times2^{n_{hat}})\"](\"https:\/\/nanzhou.cc\/wp-content\/ql-cache\/quicklatex.com-1f82a2a334d84881a2b6beb5dd550672_l3.png\" "\\"Rendered")
solution. Given ![\"n_{people}=10\"](\"https:\/\/nanzhou.cc\/wp-content\/ql-cache\/quicklatex.com-bf9aeeca31368474207f59a6034167a3_l3.png\" "\\"Rendered")
and ![\"n_{hat}=40\"](\"https:\/\/nanzhou.cc\/wp-content\/ql-cache\/quicklatex.com-2326c36321da56e33fc2248fbb1ca227_l3.png\" "\\"Rendered")
, this solution will get TLE. <\/p>\n\n\n\n
\/\/ n_people; n_hat \n\/\/ i here is the index of people\nalg[i][visited] = \n alg[i + 1][visited | num_to_hat_index[hat]] if num_to_hat_index[hat] not in visited && hat in hats[i] for hat in [0, 40]<\/code><\/pre>\n\n\n\nWe could think on the other hand: let the hat choose people. Then the complexity becomes ![\"O(n_{people}\times n_{hat}\times2^{n_{people}})\"](\"https:\/\/nanzhou.cc\/wp-content\/ql-cache\/quicklatex.com-43c1355aaf4f667dad38339af4a3165a_l3.png\" "\\"Rendered")
<\/p>\n\n\n\n
\/\/ i here is the index of hat\nalg[i][visited]\n 1. alg[i + 1][visited | (1 << j)] if (1 << j) & visited == 0 && distinct_hat[i] in people_to_hat_set[j] for j in [0, n - 1] \n 2. alg[i + 1][visited] \/\/ ith hat could not be chosen\n\/\/ alg[n_hat][(1 << n_people) - 1] = 1<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…<\/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-1056","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\/1056","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=1056"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1056\/revisions"}],"predecessor-version":[{"id":1141,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1056\/revisions\/1141"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
It is not difficult to get the following However, if we adopt the following state definition, the complexity reduces to It is not difficult to get the following However, if we use the same arithmetic difference technique, we can reduce the complexity to It is not difficult to get the following However, since It is not difficult to get the However, as we could see, the nested loop which enumerates the next It is not difficult to get the Actually, given any It is not difficult to get the We could think on the other hand: let the hat choose people. Then the complexity becomes Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…<\/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-1056","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\/1056","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=1056"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1056\/revisions"}],"predecessor-version":[{"id":1141,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1056\/revisions\/1141"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}O(n^2logn)<\/code> solution. <\/p>\n\n\n\nalg[i][j] = \n alg[j][pos], let num=2*nums[j]-nums[i] in pos = lower_bound(num_to_pos[num], j + 1)<\/code><\/pre>\n\n\n\nO(n^2)<\/code>. A tricky part is that the difference seems to be of O(n^2)<\/code> complexity for an array. But here, the difference for each i will only be O(n)<\/code> because of j > i<\/code>.<\/p>\n\n\n\n\/\/ vector<unordered_map>\nalg[i][diff]: sequence starting at i with different==diff\n\nlet diff=nums[j]-nums[i] in \n alg[i][diff] = max {\n diff in alg[j] ? alg[j][diff] + 1 : 2; for j in [i+1, n-1]}<\/code><\/pre>\n\n\n\nLC 446. Arithmetic Slices II – Subsequence<\/a><\/h4>\n\n\n\n
O(n^3)<\/code> solution.<\/p>\n\n\n\nalg[i][j] = \n sum{ alg[j][k] == 0 ? 1 : alg[j][k] + 1 if nums[k] == 2 * nums[j] - nums[i] for k in [j+1, n-1] }\n\/\/ alg[j][k] + 1 because {nums[i] : sequence[j][k]} + {nums[i], nums[j], nums[k]}<\/code><\/pre>\n\n\n\nO(n^2)<\/code>. An annoying thing here is that we only count subsequences of length >= 3<\/code>. We could use two tables to store subsequences of different lengths. <\/p>\n\n\n\n \/\/ sequence length > 2 \nalg[i][diff] = let diff = alg[j] - alg[i] in \n sum{ {diff in alg[j] ? alg[j][diff] : 0} + {diff in alg2[j] ? alg2[j][diff] : 0} for j in [i + 1, n - 1]}\n result += sum {alg[i].vals}\n \n\/\/ sequence length == 2\nalg2[i][diff] = let diff = alg[j] - alg[i] in \n alg2[i][diff]++ for j in [i + 1, n - 1]<\/code><\/pre>\n\n\n\nLC 1187. Make Array Strictly Increasing<\/a><\/h4>\n\n\n\n
O(mnlog(n))<\/code> solution.<\/p>\n\n\n\n\/\/ prev is in arr1[i - 1]::arr2\nalg[i][prev] = \n 1. if arr1[i] > prev\n 1) alg[i + 1][arr1[i]] \n \/\/ greadily choose the smallest larger one\n 2) 1 + alg[i + 1][j], j = upper_bound(arr2, prev); \n 2. if arr1[i] <= prev\n 1) 1 + alg[i + 1][j], j = upper_bound(arr2, prev); <\/code><\/pre>\n\n\n\nprev<\/code> is always in arr1[i - 1]::arr2<\/code>, we could solve the problem in O(mn)<\/code> by enumerating the index of prev<\/code>. The advantage of using an index is that the next greater element is index+1<\/code>.<\/p>\n\n\n\n\/\/ starting at i, previous is arr2[j], if j == n, it means it is arr1[i - 1]\nalg[i][j] = \n 1. if arr1[i] > arr2[j] && j in [0, n - 2] \n 1) alg[i + 1][n]\n 2) 1 + alg[i + 1][j + 1]\n 2. if arr1[i] <= arr2[j] && j in [0, n - 2] \n 1) 1 + alg[i + 1][j + 1]\n 3. if arr1[i] > arr1[i - 1] && j == n\n 1) alg[i + 1][n] \n 2) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()\n 4. if arr[i] <= arr1[i - 1] && j == n\n 1) alg[i + 1][k], k = arr2.upper_bound(arr1[i]) - arr2.begin()\n 5. if arr1[i] > arr2[j] && j == n - 1\n 1) alg[i + 1][n]\n 6. othercases will be -1<\/code><\/pre>\n\n\n\nLC 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons<\/a><\/h4>\n\n\n\n
O(nm^2K)<\/code> solution. <\/p>\n\n\n\nalg[i][k][prev_max] = sum {\n 1. prev_max * alg[i + 1][k][prev_max]\n 2. alg[i + 1][k + 1][j] for j in [prev_max + 1, m]\n\n\/\/ alg[n][k][j] = 1 for j in [1, m]<\/code><\/pre>\n\n\n\nprev_max<\/code> could be achieved by the prefix sum technique. To make implementation easier, I use another table to store prefix sum, which reduces the complexity to O(nmK)<\/code>.<\/p>\n\n\n\nalg[i][k][prev_max] = sum {\n 1. prev_max * alg[i + 1][k][prev_max]\n 2. alg2[i + 1][k + 1][prev_max+1] == sum {alg[i + 1][k + 1][j] for j in [prev_max + 1, m]}\n\n\/\/ alg[n][k][j] = 1 for j in [1, m]\n \n\/\/ alg2[i][k][m] = alg[i][k][m]\nalg2[i][k][j] = alg[i][k][j] + alg2[i][k][j + 1]<\/code><\/pre>\n\n\n\nLC 514. Freedom Trail<\/a><\/h4>\n\n\n\n
O(nm^2)<\/code> solution.<\/p>\n\n\n\n\/\/ ring m, key n\n\/\/ ch_to_index is for ring\nalg[j][i]\n = cost(i, k) + alg[j + 1][k] for k in ch_to_index[key[j]]]<\/code><\/pre>\n\n\n\nkey[j]<\/code> and the current position i<\/code> at ring, we could greedily choose two same characters in ring: the nearest right and the nearest left. We could preprocess this in O(26mlogm)<\/code> time. Then the time complexity reduces to O(nm)<\/code>. <\/p>\n\n\n\nalg[j][i]\n = min(cost(i, left) + alg[j + 1][left], cost(i, right) + alg[j + 1][right])<\/code><\/pre>\n\n\n\nLC 1434. Number of Ways to Wear Different Hats to Each Other<\/a><\/h4>\n\n\n\n
solution. Given and , this solution will get TLE. <\/p>\n\n\n\n\/\/ n_people; n_hat \n\/\/ i here is the index of people\nalg[i][visited] = \n alg[i + 1][visited | num_to_hat_index[hat]] if num_to_hat_index[hat] not in visited && hat in hats[i] for hat in [0, 40]<\/code><\/pre>\n\n\n\n<\/p>\n\n\n\n\/\/ i here is the index of hat\nalg[i][visited]\n 1. alg[i + 1][visited | (1 << j)] if (1 << j) & visited == 0 && distinct_hat[i] in people_to_hat_set[j] for j in [0, n - 1] \n 2. alg[i + 1][visited] \/\/ ith hat could not be chosen\n\/\/ alg[n_hat][(1 << n_people) - 1] = 1<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"