最佳加法表达式(dp)

题目描述：

有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中，值最小的那个表达式的值是多少 (本题只能用于整数)

解题思路：

假定数字串长度是n，添完加号后,表达式的最后一个加号添加在第 i 个数字后面，那么整个表达式的最小值，

就等于在前 i 个数字中插入 m – 1 个加号所能形成的最小值，加上第 i + 1到第 n 个数字所组成的数的值（i从1开始算）。

设dp(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值，那么：

if m = 0

　　dp(m,n) = n个数字构成的整数

else if n < m + 1

　　 dp(m,n) = ∞

else

　　 dp(m,n) = Min{ dp(m-1,i) + Num(i+1,n) } ( i = m … n-1)

Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操作复杂度是O(j-i+1)，可以预处理后存起来。总时间复杂度：O(mn2) .

代码：

#include<iostream>

#include<cstring>

using namespace std;

#define N  100 + 5

#define INF 0x3f3f3f

int dp[N][N];

int num[N][N];

int v[N];

int main() {

    int n, m;

    while(cin >> n >> m) {

        for(int i = ; i <= n; i++) cin >> v[i];

        for(int i = ; i <= n; i++) {

            num[i][i] = v[i];

            for(int j = i + ; j <= n; j++) {

                num[i][j] = num[i][j-]* + v[j];//预处理，方便取出从i到j的值

            }

        }

        memset(dp, 0x3f, sizeof(dp));//把dp初始化为无穷大

        for(int i = ; i <= n; i++) {

            dp[][i] = num[][i];

        }

        for(int i = ; 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-][k] + num[k+][j]);

                }

            }

        }

        printf("%d\n", dp[m][n]);

    }

    return ;

}

巴特西

最佳加法表达式(dp)

最新文章

热门文章