算法证明 - 从 n 位数字中删除 k 位数字后构建最小数字

Question

Problem: given an n-digit number, which k (k < n) digits should be deleted from it to make the number left is the smallest among all cases (the relative sequence of remaining digits should not be changed). e.g. delete 2 digits from '24635', the smallest left number is '235'.

解决方案:删除大于或等于其右邻居的第一个数字(从左到右)，或者如果我们找不到这样的数字，则删除最后一个数字。重复此过程 k 次。 (参见 codecareer 引用。还有其他解决方案，例如 geeksforgeeks 、 stackoverflow ，但我认为这里描述的更直观，所以我更喜欢这个。)

现在的问题是，如何证明上面的解法是正确的，即如何保证最后的数是最小的，每一步都删掉一个数后使最后的数最小。

Answer 1

假设 k = 1 .

让m = Σ<sub>i=0,...,n</sub> a<sub>i</sub>b<sup>i</sup>和 n+1位数 a<sub>n</sub>a<sub>n-1</sub>...a<sub>1</sub>a<sub>0</sub>带底座 b ，即 0 ≤ a<sub>i</sub> < b ∀ 0 ≤ i ≤ n (例如 b = 10 )。

证明

∃ j > 0与 a<sub>j</sub> > a<sub>j-1</sub>让j最大。
这意味着 a<sub>j</sub>是(严格来说不一定)递增的连续数字序列的最后一位。 然后是数字 a<sub>j</sub>现在已从号码和结果号码中删除 m'有值(value)

m' = Σi=0,...,j-1 aibi   +   Σi=j+1,...,n aibi-1

这种减少的目的是最大化差异m-m' .那么让我们来看看:

m - m' = Σi=0,...,n aibi - (Σi=0,...,j-1 aibi   +   Σi=j+1,...,n aibi-1)
       = ajbj + Σi=j+1,...,n (aibi - aibi-1)
       = anbn + Σi=j,...,n-1 (ai - ai+1)bi

有没有更好的选择j获得更大的差异？

• 自 a<sub>n</sub>...a<sub>j</sub>是递增子序列，a<sub>i</sub>-a<sub>i+1</sub> ≥ 0持有。所以选择j' > j而不是 j ，你得到更多的零，你现在有一个正数，即差异不会变大，但如果存在 i 会变小与 a<sub>i+1</sub> < a<sub>i</sub> (严格更小)。
• j应该是最大的，即 a<sub>j-1</sub>-a<sub>j</sub> < 0 .我们知道

  bj-1 > Σi=0,...,j-2(b-1)bi = bi-1-1

  这意味着，如果我们选择 `j' < j'，我们会得到差值的负数，因此它也不会变大。

如果∄ j > 0与 a<sub>j</sub> > a<sub>j-1</sub>以上证明适用于 j = 0 .

还有什么事要做？

这只是证明您的算法适用于 k = 1 .

可以将上述证明扩展到(不一定严格)递增数字的多个子序列。由于您需要的索引数量，它的证明完全相同，但可读性要差得多。

也许你也可以使用归纳法，因为数字之间没有相互作用(阻止下一个选择或其他东西)。