Delete Digits怎样证明是最优解?# JobHunting - 待字闺中
s*p
1 楼
这道题:
Given string A representative a positive integer which has N digits, remove
any k digits of the number, the remaining digits are arranged according to
the original order to become a new positive integer.
Find the smallest integer after remove k digits.
N <= 240 and k <= N,
在网上看到一些答案, 说是每次删除剩下string里面第一个A[i] > A[i+1] 的数,重复K
次. 这对于每一步是局部最优解, 但我没想明白为什么这样做的是全局最优解.
这个怎么证明?
Given string A representative a positive integer which has N digits, remove
any k digits of the number, the remaining digits are arranged according to
the original order to become a new positive integer.
Find the smallest integer after remove k digits.
N <= 240 and k <= N,
在网上看到一些答案, 说是每次删除剩下string里面第一个A[i] > A[i+1] 的数,重复K
次. 这对于每一步是局部最优解, 但我没想明白为什么这样做的是全局最优解.
这个怎么证明?
