lintcode-741. Calculate Maximum Value II题解
2018-06-17 21:01:02来源:未知 阅读 ()
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]; } };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Maximum White Subtree 2020-03-26
- 【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/ 2019-08-26
- HDU6298 Maximum Multiple (多校第一场1001) 2018-09-05
- Uncaught RangeError: Maximum call stack size exceeded 调 2018-06-18
- Sum of Two Integers 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash