有一个由数字1,2,…….9组成的数字串长度不超过200问如何将m个加号插入到这个数字串中,使所形成的算术表达式的值最小,写出它的代码
时间: 2023-06-11 07:07:36 浏览: 62
这是一个经典的动态规划问题,可以使用贪心算法和动态规划算法解决。下面是使用动态规划算法的解法:
假设dp[i][j]表示将前i个数字分成j段所能得到的最小值,那么状态转移方程为:
dp[i][j] = min{dp[k][j-1] + cost(k+1, i)} (j-1<=k<i)
其中,cost(i, j)表示将数字串中i到j之间的数字组成一个数的代价,这里的代价指的是该数字串所代表的数的值。
具体实现代码如下:
```python
def solve(num_list, m):
n = len(num_list)
# 计算cost数组
cost = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
for j in range(i+1, n):
num_str = ''.join(num_list[i:j+1])
cost[i][j] = int(num_str)
# 初始化dp数组
dp = [[float('inf')] * (m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = 0
# 动态规划求解
for i in range(1, n+1):
for j in range(1, m+1):
for k in range(j-1, i):
dp[i][j] = min(dp[i][j], dp[k][j-1] + cost[k+1][i])
return dp[n][m]
# 测试
num_list = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
m = 3
print(solve(num_list, m)) # 输出结果为 123+45+6+7+8+9=198
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)