{"id":857,"date":"2020-03-28T22:33:44","date_gmt":"2020-03-29T05:33:44","guid":{"rendered":"http:\/\/209.126.2.187\/?p=857"},"modified":"2020-05-16T10:33:05","modified_gmt":"2020-05-16T17:33:05","slug":"linear-dp-real-result","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/28\/linear-dp-real-result\/","title":{"rendered":"DP in Linear Structures & Real Result"},"content":{"rendered":"\n

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

Some problems require returning real result not just a number. <\/p>\n\n\n\n

To do this, a good method is that we create another table to store the optimal choices we made on each state. <\/p>\n\n\n\n

To return any optimal result, the choice<\/code> table will be as large as the alg<\/code> table. The result can we achieved by a loop. <\/p>\n\n\n\n

The return all the results, the choice<\/code> table needs one more dimension (a vector) to store all optimal choices at each state. Results could be retrieved by backtracking. <\/p>\n\n\n\n

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

Return all Longest Common Subsequence<\/h4>\n\n\n\n

The length of the LCS is not difficult.<\/p>\n\n\n\n

<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[alg[i][j] = max(1 + alg[i + 1][j + 1]\ if a[i] == b[j], alg[i][j + 1], alg[i + 1][j])\]\"<\/p><\/p>\n\n\n\n

We could use another 3D vector to store the choices we made at each state and do backtracking to get all LCS strings. <\/p>\n\n\n\n

\/\/ choice\nvector<vector<vector<int>>> choice;\nfor (int i = m - 1; i >= 0; --i) {\n for (int i = m - 1; i >= 0; --i) {\n    for (int j = n - 1; j >= 0; --j) {\n        int choice1 = 0, choice2, choice3;\n        if (a[i] == b[j]) {\n            choice1 = 1 + alg[i + 1][j + 1];\n        } \n        choice2 = alg[i][j + 1];\n        choice3 = alg[i + 1][j];\n        int max_ = max(choice1, max(choice2, choice3));\n        if (max_ == choice1) {\n            choice[i][j].push_back(1);\n        }\n        if (max_ == choice2) {\n            choice[i][j].push_back(2);\n        }\n        if (max_ == choice3) {\n            choice[i][j].push_back(3);\n        }\n        alg[i][j] = max_;\n    }\n}<\/code><\/pre>\n\n\n\n
LC 1449. Form Largest Integer With Digits That Add up to Target<\/a><\/h4>\n\n\n\n
The problem is a typical knapsack problem. It requires that you choose as many as possible digits that cost sums up to target. Among the results with the same length, choose the lexicographically largest one. <\/p>\n\n\n\n
The problem can be solved by a typical DP which stores the optimal solution at each state as a string. But by introducing string comparison, the worst complexity will be O(9*target^2)<\/code>.<\/p>\n\n\n\n
\/\/ reverse cost, so that it goes from digit 9 to 1\nalg[i][j] = max_ {\n  1. alg[i + 1][j]\n  2. \"10 - i\" + alg[i][j - cost[i]]\n}\n\/\/ alg[10][0] = \"\"\n\/\/ max_ first compares length, then lexicographic order<\/code><\/pre>\n\n\n\n
However, we could do better by storing the length and greedily choose the larger digit at each state. Normally we use another table choice to record the optimal choices we made at each state.   <\/p>\n\n\n\n
alg[i][j] = max_ {\n  1. alg[i + 1][j]\n  2. 1 + alg[i][j - cost[i]]\n}\nchoice[i][j] = {\n  1. {false} if choose alg[i + 1][j] at alg[i][j]\n  2. {true}  if choose alg[i][j - cost[i]] at alg[i][j]\n  3. {false, true} if both are equal\n}\n\/\/ i = 1, j = target,\nif choice[i][j] == {false, true}:\n  we add this digit first since the digit (10 - i) is larger\n  j -= cost[i]\nelse:\n  choose what is in choice[i][j]<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…<\/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-857","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\/857","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=857"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/857\/revisions"}],"predecessor-version":[{"id":1230,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/857\/revisions\/1230"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=857"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=857"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=857"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}