math proof for the greedy solution
key lemma: \nminimal (m + 1)-digit number contains minimal m-digit number for all m = 0, 1, ..., n - 1\n\nproof:\n\ngreedy solution to delete one digit from som
**key lemma:** \n```minimal (m + 1)-digit number contains minimal m-digit number for all m = 0, 1, ..., n - 1```\n\nproof:\n\n**greedy solution to delete one digit from some number to get the minimal result**: ```just delete the first digit which next digit is smaller than it, or the last digit if digits are in non-decending order```. This is very easy to prove.\n\nwe use contradiction to proof the lemma.\n\nsuppose the first time the lemma is broken when ***m = k***, **so *S(k) \u2284 S(k + 1)***. Notice that the ***S(k) \u2282 S(n)*** as the initial number contains all sub optimal ones, so there must exist a ***x*** that ***S(k) \u2282 S(x)*** and ***S(k) \u2284 S(x - 1), k + 2 <= x <= n***\nwe use the greedy solution above to delete only one digit ***S[X][y]*** from ***S(x)*** to get ***S(x - 1)*** , so **S[X][y] \u2208 S(x)** and ***S[X][y] \u2209 S(x - 1)*** and ***S(k)*** must contain ***S[X][y]*** . We now use **contradiction** to prove that ***S(k)*** does ***not*** need to contain this digit .\n\nAccording to our greedy solution, ```all digits from beginning to S[X][y] are in non-desending order.```\n\n1. if ***S[X][y]*** is at the ***tail***, then ***S(k)*** can be the **first k digits of S(x)** ---> contradiction!\n2. otherwise, we firstly know that **all digits in S[X][1, 2,..., y] are in S[k]**. If there is a ***S[X][z]*** is not in ***S(k)*** , 1 <= z <= y - 1, then **we can shift digits of S(k) that in range S[X][z + 1, y] left by one unit to get one smaller than or equals S(k).**  Therefore, there are **at least 2 digit after S[X][y] that are not in S(k) as x >= k + 2**. Then, we can **follow the prefix of S(k) to S[X][y]**, but we **do not use S[X][y], we use from S[X][y + 1]. As S[X][y + 1] < S[X][y], we can build a smaller S(k)** -------> contradiction!\n\nso, we prove lemma. ```If we have got S(m + 1), and we know S(m + 1) contains S(m), then S(m) must be the smallest number after removing one digit from S(m + 1)```
[]