首页 > 代码库 > 字符串中插入加号（dp）动态规划
字符串中插入加号（dp）动态规划
题目：长度为m的字符串插入n个加号求最小和。例如string str="123456",n=2;输出12+34+56的和为102，同时输出2 4，也就是加号位置。下面为实现思路：
实现过程主要就是区间dp的思想，其中状态转移方程为dp[i][j] = min(dp[k][j - 1] + getnum(str.substr(k, i-k)), dp[i][j]);//其中dp[i][j]表示1-i中使用了j个加号，在这里我用struct主要就是记录加号的位置。
#include<iostream> #include<ctime>#include<vector>#include<string>#include<algorithm>#include<sstream>using namespace std;//把字符串转化成对应的整数例如字符串"123"的getnum值就是123int getnum(string str){ if (str.size() <= 0)return 0; int sum = 0; for (int i = 0; i < str.size(); i++) { sum = 10 * sum + (str[i] - ‘0‘); } return sum;}//把字符串中每个数字分别相加例如"123"的getnum1就是6int getnum1(string str){ int sum = 0; for (int i = 0; i < str.size(); i++) { sum = sum + (str[i] - ‘0‘); } return sum;}struct node{ int value; int k;};int main(){ string str = "1234567891"; int n = 3; int m = str.size(); vector<vector<node>>dp(m + 1, vector<node>(n+1)); for (int i = 0; i < m+1; i++) { for (int j = 0; j < n+1; j++) { dp[i][j].value = http://www.mamicode.com/9999999;" "; } cout << endl; cin.get(); return 0;}
字符串中插入加号（dp）动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。