C++ Top-Down Recursive DP O(n*m)


  • 0
    A
    #define inf  0x3f3f3f
        
    class Solution {
        public:
        vector < vector < int > > dp;
        
        int findMinimumAscii(string &s, string &t, int p, int q) {
            if(p == s.size() and q == t.size()) {
                return 0;
            }
            if(p == s.size()) {
                int sum = 0;
                for(int i = q; i < t.size(); i++) {
                    sum += t[i];
                }
                return sum;
            }
            
            if(q == t.size()) {
                int sum = 0;
                for(int i = p; i < s.size(); i++) {
                    sum += s[i];
                }
                return sum;
            }
            if(dp[p][q] != -1) {
                return dp[p][q];
            }
            int ans = inf;
            int cost = (s[p] == t[q] ? 0 : s[p] + t[q]);
            ans = min(findMinimumAscii(s, t, p + 1, q) + s[p], 
                  min(findMinimumAscii(s, t, p, q + 1) + t[q], 
                      findMinimumAscii(s, t, p + 1, q + 1) + cost));
            dp[p][q] = ans;
            return ans;
        }
        int minimumDeleteSum(string s1, string s2) {
            dp.assign(s1.size(), vector < int >(s2.size(), -1));
            return findMinimumAscii(s1, s2, 0, 0);
        }
    };
    

Log in to reply
 

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