有一个由数字1-9组成的数字串（长度不超过200），问如何将M（1<=M<=200）个加号插入这个数字串中，使得所形成的算术表达式的值最小。
- 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻
- M的值一定小于数字串的长度
例如：数字串79846，若需加入两个加号，则最佳方案是79+8+46，算术表达式的值为133。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200;
//const int INF = 0x3f3f3f3f;
int dp[N][N];
int num[N][N];
int m;
char ch[N];//算从第k个数字到第p个数字(不包括)组成的值
int NUM(int k, int p) {//num里的元素初始化为-1，如果不等于-1，则表示已得到结果if (num[k][p] != -1) {return num[k][p];}int sum = 0;for (int i = k; i<p; i++) {sum = sum * 10 + ch[i] - '0';}num[k][p] = sum;return sum;
}//前p个数字加m个加号的最小值
int DP(int p, int m) {//dp里的元素初始化为-1，如果不等于-1，则表示已得到结果if (dp[p][m] != -1) {return dp[p][m];}if (m == 0) {//如果加号个数为0dp[p][0] = NUM(0, p);return dp[p][0];}//赋一个const类型的值，表示dp[p][m]一旦有了值以后就不允许通过赋值来改变它//这里用无穷大值INF = 0x3f3f3f3f的意义是？我随便用个const int类型的值都可以啊dp[p][m] = N;for (int i = p - 1; i>=m; i--) {dp[p][m] = min(dp[p][m], DP(i, m - 1) + NUM(i, p));//(右侧)dp[p][m]相当于一个以前较小值,//DP(i,m-1)相当于前i个数字(不包括)加m-1个加号的较小值,//dp[p][m]=min(dp[p][m],DP(i,m-1)+NUM(i,p)),等式左侧dp[p][m]为新找到的较小值}return dp[p][m];
}int main() {//使用memset函数调用内存，并初始化为-1memset(dp, -1, sizeof(dp));memset(num, -1, sizeof(num));cin >> ch;cin >> m;int len = strlen(ch);cout << DP(len, m) << endl;system("pause");return 0;
}
看别人的代码都定义了const int INF = 0x3f3f3f3f;我是真的搞不明白用这个的作用在哪里，毕竟也是第一次见到，第一次了解。去搜了一下，也只找到了使用“无穷大”的好处，要是有知道这个问题为什么要用INF = 0x3f3f3f3f;的大佬，还希望在评论区留言帮帮孩子
