lintcode-741. Calculate Maximum Value II题解

741. Calculate Maximum Value II

Given a string of numbers, write a function to find the maximum value from the string, you can add a + or * sign between any two numbers，It's different with Calculate Maximum Value, You can insert parentheses anywhere.

样例
Given str = 01231, return 12
(0 + 1 + 2) * (3 + 1) = 12 we get the maximum value 12

Given str = 891, return 80
As 8 * (9 + 1) = 80, so 80 is maximum.

 

解题思路：动态规划  总耗时: 562 ms

其中DP[i][j]表示从第i个字符到第j个字符所能得到的算式的最大值。
递归算式为DP[i][j] = max(DP[i][m]+DP[m+1][j],DP[i][m]*DP[m+1][j]) 其中i<=m<j;

 

class Solution {
public:
    /**
     * @param str: a string of numbers
     * @return: the maximum value
     */
    int maxValue(string &str) {
        // write your code here
        int size = str.size();
        if(size == 0) return 0;
        vector<int> nums;
        for(auto c:str) nums.push_back(c-'0');        //把原始string转换成数字数组，方便后面访问
        vector<vector<int>> DP(size,vector<int>(size,0));    //建立DP矩阵，这里是二维的
        for(int i = 0; i < size; ++i) DP[i][i] = nums[i];    //初始化所有只含一个字符的为原始值
        for(int step = 1; step < size; ++step){            //最外层是DP[i][j]之中j-i的step值，需要从小到大获取
            for(int s = 0; s < size - step; ++s){        //在每个step情况下获取所有值
                int temp = 0;
                for(int mid = s; mid < s + step ;++mid){        //递归公式，获得当前区域最大值
                    temp = max(temp,max(DP[s][mid]+DP[mid+1][s+step],DP[s][mid]*DP[mid+1][s+step]));
                }
                DP[s][s+step] = temp;
            }
        }
        return DP[0][size-1];
    }
};