@tashia Thanks for asking. In optimization rule 1, we first create the largest number from each array separately WITHOUT LENGTH CONSTRAINT, and as a result, these numbers we create must be non-strictly decreasing. For your case, we can not apply k=4 directly, since the largest number we can create from nums1 is '9' without length constraint, and also '9' for nums2. Then we say the largest number we can create from these two arrays without length constraint is '99'. The value of k is not a constraint, it should be a result. For your case, k=2. And if we want to get the largest number for k=1. Trim it.
Try hard to understand how did you work this out!
search start is simple - start looking for next maximum number from index of previous maximum
But how much span of array should be? If i am to choose 5 items from an item of 6, and I am choosing 2nd item (selects is 4) then I should range so that there're at least 3 items left once i choose maximum, the only guaranteed way to do this is that search span ends before 3 rd item. How did you work this out? Can somebody explain???
@solocaptain It looks like DP O(mnk) solution will visit many unnecessary sub-problems. I can't give a strict proof that how many unnecessary sub-problems it visited, but we can see an example: string one is 911111111119, and string two is 911111111119, and we are looking for a four-digit max number. The answer is 9999. But if we use DP, then we consider lots of unnecessary sub-problems like (11111111119,11111111119,4), etc. So we can try greedy method. In conclusion, DP method is correct, but the method had visited lots of unnecessary sub-problems, so it's a better idea to try greedy method after you have a DP method.
I also couldn't understand the meaning of the quesion according to the examples provided at frst. After seeing some answers of the quesion, I think " the maximum number of length k " means the maximum "string" in lexicographic ordering of length k. Only in this way can the examples be right.