Some Interval DP Problems and State Reduction

Правка en22, от lelbaba, 2022-11-08 11:09:08

Hi everyone! Recently I have been solving some classic interval DP problems, and came across some neat problems. Most of these problems have relatively simple recurrence relations, but the straightforward solutions will not pass in complexity, hence requires an observation to reduce the complexity (generally by reducing the number of states by some pre-computation).

Prerequisites : Introductory interval DP such as Longest Increasing Subsequence, Longest Common Subsequence.

1312E - Array Shrinking

You are given an array of $$$a_1,a_2,\dots,a_n$$$ length $$$n \ (n \leq 500, 1 \leq a_i \leq 1000).$$$ You can perform the following operation any number of times:

  • Choose a pair of two neighboring equal elements $$$a_i=a_{i+1}$$$ (if there is at least one such pair).
  • Replace them by one element with value $$$a_i + 1$$$. After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array a you can get?
Solution
Теги dynamic programming, intervals, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en50 Английский lelbaba 2022-11-10 16:10:07 1209 (published)
en49 Английский lelbaba 2022-11-10 15:01:42 2223
en48 Английский lelbaba 2022-11-10 12:54:16 22
en47 Английский lelbaba 2022-11-10 12:49:56 3580
en46 Английский lelbaba 2022-11-10 12:26:40 14
en45 Английский lelbaba 2022-11-10 12:22:40 36
en44 Английский lelbaba 2022-11-10 12:18:22 20
en43 Английский lelbaba 2022-11-10 12:16:59 881
en42 Английский lelbaba 2022-11-10 12:14:13 1357
en41 Английский lelbaba 2022-11-10 10:57:02 1313
en40 Английский lelbaba 2022-11-08 16:11:57 4
en39 Английский lelbaba 2022-11-08 16:11:22 1314
en38 Английский lelbaba 2022-11-08 15:27:56 221
en37 Английский lelbaba 2022-11-08 15:20:41 71
en36 Английский lelbaba 2022-11-08 15:13:23 11
en35 Английский lelbaba 2022-11-08 15:12:32 1262
en34 Английский lelbaba 2022-11-08 14:45:23 777
en33 Английский lelbaba 2022-11-08 14:18:25 70
en32 Английский lelbaba 2022-11-08 14:16:32 49
en31 Английский lelbaba 2022-11-08 14:13:37 121
en30 Английский lelbaba 2022-11-08 14:11:03 188
en29 Английский lelbaba 2022-11-08 13:58:38 58
en28 Английский lelbaba 2022-11-08 13:57:19 5 Tiny change: '$f_{i,j,k} denote wh' -> '$f_{i,j,k}$ denote wh'
en27 Английский lelbaba 2022-11-08 13:56:26 921
en26 Английский lelbaba 2022-11-08 11:12:27 2 Tiny change: 'elation,\n\n$f_{l,l}' -> 'elation,\n$f_{l,l}'
en25 Английский lelbaba 2022-11-08 11:11:52 2 Tiny change: 'elation,\n$f_{l,l}' -> 'elation,\n\n$f_{l,l}'
en24 Английский lelbaba 2022-11-08 11:10:41 4 Tiny change: 'elation,\n\n$f_{l,l} = a_l$\n\n$f_{l,r}' -> 'elation,\n$f_{l,l} = a_l$\n$f_{l,r}'
en23 Английский lelbaba 2022-11-08 11:09:46 4
en22 Английский lelbaba 2022-11-08 11:09:08 5
en21 Английский lelbaba 2022-11-08 11:07:39 4
en20 Английский lelbaba 2022-11-08 11:05:47 1 Tiny change: 'rations.\n\n<spoiler' -> 'rations.\n<spoiler'
en19 Английский lelbaba 2022-11-08 11:04:51 2 Tiny change: 'i} + 1)$\nNote: $[' -> 'i} + 1)$\n\nNote: $['
en18 Английский lelbaba 2022-11-08 11:03:12 22 Tiny change: 'dp_1 = 1.$\n</spoile' -> 'dp_1 = 1.$ $dp_n$ is our answer.\n</spoile'
en17 Английский lelbaba 2022-11-08 11:01:56 18 Tiny change: '+ f_{j,i}$\n</spoil' -> '+ f_{j,i}$ where $dp_1 = 1.$\n</spoil'
en16 Английский lelbaba 2022-11-08 10:59:52 2 Tiny change: 'j \leq i, f_{j,i} \' -> 'j \leq i, \ f_{j,i} \'
en15 Английский lelbaba 2022-11-08 10:59:09 4 Tiny change: 'i} \ne 0} dp_{j-1} ' -> 'i} \ne 0} \ \ dp_{j-1} '
en14 Английский lelbaba 2022-11-08 10:58:27 237
en13 Английский lelbaba 2022-11-08 10:41:39 4 Tiny change: 'relation, //\n$f_{l,l}' -> 'relation, \\\n$f_{l,l}'
en12 Английский lelbaba 2022-11-08 10:41:09 76
en11 Английский lelbaba 2022-11-08 10:38:21 2 Tiny change: '{l,i} + 1)\n</spoile' -> '{l,i} + 1)$\n</spoile'
en10 Английский lelbaba 2022-11-08 10:37:57 158
en9 Английский lelbaba 2022-11-08 10:24:51 5
en8 Английский lelbaba 2022-11-08 10:22:29 233
en7 Английский lelbaba 2022-11-08 10:18:02 292
en6 Английский lelbaba 2022-11-08 09:37:52 9 Tiny change: 'ed to.\n\n#### Claim\nIf the s' -> 'ed to.\n\n**Claim**\nIf the s'
en5 Английский lelbaba 2022-11-08 09:36:52 305
en4 Английский lelbaba 2022-11-08 09:08:05 63
en3 Английский lelbaba 2022-11-08 09:03:16 98
en2 Английский lelbaba 2022-11-08 08:28:51 65
en1 Английский lelbaba 2022-11-08 08:19:37 1038 Initial revision (saved to drafts)