# Dynamic programming solution in CPP.

• As the initial process, I 'fetch' all the numbers and the operators in the string. In the code, I use range[i][j] to represent all the possible result in the number range i to j. Then comes the range DP process.

``````#include<set>
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int>ret;
fetch(input);
int numNum=num.size();
for(int i=0;i<numNum;i++)
{
vector<vector<int> >vec;
for(int j=0;j<numNum;j++)
{
vector<int>see;
vec.push_back(see);
}
range.push_back(vec);
}

for(int i=0;i<numNum;i++) range[i][i].push_back(num[i]);
for(int i=0;i<numNum-1;i++) range[i][i+1].push_back(getRes(num[i],num[i+1],op[i]));
for(int len=3;len<=numNum;len++)
{
for(int i=0;i+len-1<numNum;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
{
int firSize=range[i][k].size(),secSize=range[k+1][j].size();
for(int fir=0;fir<firSize;fir++)
{
for(int sec=0;sec<secSize;sec++)
{
range[i][j].push_back(getRes(range[i][k][fir],range[k+1][j][sec],op[k]));
}
}
}
}
}
return range[0][numNum-1];
}
private:
vector<int>num;
vector<char>op;
vector<vector<vector<int> > >range;
void fetch(string input)
{
int temp;
int len=input.length();
int i;
bool negeFir;
if(input[0]=='+') i=1;
else if(input[0]=='-') negeFir=true,i=1;
else negeFir=false,i=0;
for(int i=0;i<len;i++)
{
temp=0;
while(i<len&&isnum(input[i]))
{
temp=temp*10;
temp+=input[i]-'0';
i++;
}
num.push_back(temp);
op.push_back(input[i]);
}
if(negeFir) num[0]=-num[0];
}
bool isnum(char a)
{
return a>='0'&&a<='9';
}
int getRes(int fir,int sec,char Op)
{
if(Op=='+') return fir+sec;
else if(Op=='-') return fir-sec;
else if(Op=='*') return fir*sec;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.