A iterative cpp dp code


  • 0
    T
    typedef function<int(const int&, const int&)> bfunc;
    class Solution {
    public:
        vector<int> diffWaysToCompute(string input) {
            map<char, bfunc> chToOpfunc = {
                {'+', plus<int>()},
                {'-', minus<int>()},
                {'*', multiplies<int>()}
            };
            int cnum = 0;
            vector<int> nums;
            vector<bfunc> funcs;
            for(auto ch:input){
                if(chToOpfunc.find(ch) == chToOpfunc.end()){
                    cnum = cnum*10 + (ch - '0');
                    continue;
                }
                funcs.push_back(chToOpfunc[ch]);
                nums.push_back(cnum);
                cnum = 0;
            }
            nums.push_back(cnum);
            const int N = nums.size();
            vector<vector<vector<int>>> dp(N+1);
            for(int i = 0; i < N; ++i)
                dp[1].push_back(vector<int>{nums[i]});
            for(int sz = 2; sz <= N; sz++){
                dp[sz].resize(N-sz+1);
                for(int si = 0; si + sz <= N; ++si){
                    for(int lsz = 1; lsz < sz; ++lsz){
                        auto lres = dp[lsz][si];
                        auto rres = dp[sz-lsz][si+lsz];
                        auto op = funcs[si+lsz-1];
                        for(auto lr:lres)
                            for(auto rr:rres)
                                dp[sz][si].push_back(op(lr, rr));
                    }
                }
            }
            return dp[N][0];
        }
    };

Log in to reply
 

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