Dynamic programming solution in CPP.


  • 0
    8

    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;
    }
    

    };


Log in to reply
 

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