删除数字求最小值给定一个高精度正整数a,去掉其中s个数字后按原左右次序将组成一个新的正整数对给定的a,s寻找一种方案使得剩下的数字组成的新数最小
时间: 2024-01-03 11:09:47 浏览: 80
依次去掉n中的某一位数字,得到m个整数,并将这m个整数按从小到大的次序排列后输出.docx
5星 · 资源好评率100%
这个问题可以使用动态规划来解决。
我们定义一个二维数组dp[i][j],表示从数a的第i位开始删除j个数字得到的最小数字。状态转移方程如下:
$$
dp[i][j] = \begin{cases}
0, & j=0\\
a[i] + dp[i+1][j], & j>0 \text{且} a[i] < a[i+1]\\
dp[i+1][j-1], & j>0 \text{且} a[i] \geq a[i+1]
\end{cases}
$$
其中,第一种情况表示不需要删除数字,直接返回0。第二种情况表示当前数字比后面的数字小,为了使得删除后的数字最小,我们应该删除当前数字,然后继续处理从第i+1位开始的数字。第三种情况表示当前数字比后面的数字大或相等,为了使得删除后的数字最小,我们应该保留当前数字,然后继续处理从第i+1位开始的数字,同时需要将删除的数字数量减1。
最终的结果为dp[0][s],表示从数a的第0位开始删除s个数字得到的最小数字。
以下是一个 Python 代码实现:
```python
def delete_digits(a, s):
n = len(a)
dp = [['' for _ in range(s+1)] for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(min(s, n-i)):
if j == 0:
dp[i][j] = a[i]
elif a[i] < a[i+1]:
dp[i][j] = a[i] + dp[i+1][j-1]
else:
dp[i][j] = dp[i+1][j]
return dp[0][s].lstrip('0') or '0'
```
这个函数接受一个字符串a表示的高精度正整数和一个整数s,返回删除s个数字后得到的最小数字。其中,函数调用`lstrip('0')`用于删除结果中的前导零。注意,如果删除后的数字是0,则返回字符串'0'而不是空字符串。
阅读全文