最佳加法表达式（dp）

有一个由 1..9 组成的数字串 . 问如果将 m 个加号插入到这个数字串中 , 在各种可能形成的表达式中，值最小的那个表达式的值是多少. 解题思路：第一步：确定状态。这里面有两个变量，一个是m个加号， 另一个是n个长度的字符串， 则可确定状态dp[m][n] 表示为n个字符，m个加号的最小值。既然是dp那么有一点我们必须明白，就是当前的状态一定是由以前的状态求出来，这就意味着我们一定要找出初始状态。第二步：找出初始状态。这一题很好想，初始状态一定是当有0个加号的时候。第三步也是最难的一步了：找出状态转移方程。这题里面 ： dp[i][j] = min(d[i][j], dp[i - 1][k] + digit(k + 1, j), 这里面digit(a, b)表示从第a个字符到第b个字符所代表的数字。 以上这三步应该是做dp通用的思考方法，具体的题要具体思考。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 105; const int INF = 0x3f3f3f3f; typedef long long LL; long long dp[MAXN][MAXN]; char str[MAXN]; LL getDigit(int start, int end) { LL ret = 0; while (start <= end) { ret = ret * 10 + str[start] - '0'; start++; } return ret; } int main() { int m, n; while (~scanf("%d%d", &n, &m)) { memset(dp, INF, sizeof(dp)); scanf("%s", str + 1); for (int i = 1; i <= n; i++) { dp[0][i] = getDigit(1, i); } for (int i = 1; i <= m; i++) { for (int j = i; j <= n; j++) { for (int k = i; k <= j; k++) { dp[i][j] = min(dp[i][j], dp[i - 1][k] + getDigit(k + 1, j)); } } } printf("%d\n", dp[m][n]); } return 0; }