Calculate Maximum Value II

╰半橙微兮° 2022-05-31 02:13 110阅读 0赞

http://www.lintcode.com/en/problem/calculate-maximum-value-ii/

标签是动态规划

我的思路是分治+记忆化搜索。

只有分治就能解决问题，但是超时了，用了记忆化搜索通过。

**思路：**

题目是延续了http://www.lintcode.com/en/problem/calculate-maximum-value的，这里称为上一题，上一题的思路更简单一些，就是判断每一步是乘还是加，显然左右两边有0或者1的时候加，否则乘，这题同样的思路，不过是从0到str.size()依次分为左右两边判断，判断用乘还是加的规则与上一题相同。这样一个递归就完成了。但是中间其实有很多重复计算，将中间过程存储下来就可以ac了。dp\[i\]\[j\]存储从i到j字符串的最大值。

**只有分治思路的代码：**

int maxValue(string &str) \{  
// write your code here  
if (str.size() == 0) \{  
return 0;  
\}  
if (str.size() == 1) \{  
return str\[0\] - '0';  
\}  
int left = 0, right = 0, res = 0, tmp = 0;  
for (int i = 0; i < str.size() - 1; i++) \{  
string ls = str.substr(0, i + 1);  
string rs = str.substr(i + 1, str.size() - i - 1);  
left = maxValue(ls);  
right = maxValue(rs);  
if (left \* right == 0 || left == 1 || right == 1) \{  
tmp = left + right;  
\} else \{  
tmp = left \* right;  
\}  
res = max(res, tmp);  
\}  
return res;  
\}

**加上记忆化搜索以后：**

int maxValue(string &str) \{  
if (str.size() == 0) \{  
return 0;  
\}  
if (str.size() == 1) \{  
return str\[0\] - '0';  
\}  
vector<vector<int>>dp(str.size(), vector<int>(str.size(), -1));  
for (int i = 0; i < str.size(); i++) \{  
dp\[i\]\[i\] = str\[i\] - '0';  
\}  
return help(dp, 0, str.size() - 1);  
\}  
int help(vector<vector<int>> &dp, int i, int j) \{  
if (dp\[i\]\[j\] != -1) \{  
return dp\[i\]\[j\];  
\}  
int left, right, tmp, res = 0;  
for (int b = i; b < j; b++) \{  
left = help(dp, i, b);  
right = help(dp, b + 1, j);  
if (left \* right == 0 || left == 1 || right == 1) \{  
tmp = left + right;  
\} else \{  
tmp = left \* right;  
\}  
res = max(res, tmp);  
\}  
dp\[i\]\[j\] = res;  
return res;  
\}