<p>Given two strings <code>s1</code> and&nbsp;<code>s2</code>, return <em>the lowest <strong>ASCII</strong> sum of deleted characters to make two strings equal</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;sea&quot;, s2 = &quot;eat&quot;
<strong>Output:</strong> 231
<strong>Explanation:</strong> Deleting &quot;s&quot; from &quot;sea&quot; adds the ASCII value of &quot;s&quot; (115) to the sum.
Deleting &quot;t&quot; from &quot;eat&quot; adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;delete&quot;, s2 = &quot;leet&quot;
<strong>Output:</strong> 403
<strong>Explanation:</strong> Deleting &quot;dee&quot; from &quot;delete&quot; to turn the string into &quot;let&quot;,
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting &quot;e&quot; from &quot;leet&quot; adds 101[e] to the sum.
At the end, both strings are equal to &quot;let&quot;, and the answer is 100+101+101+101 = 403.
If instead we turned both strings into &quot;lee&quot; or &quot;eet&quot;, we would get answers of 433 or 417, which are higher.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s1.length, s2.length &lt;= 1000</code></li>
	<li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li>
</ul>

class Solution {
public:
    int solve(string s1, string s2, int i, int j, vector<vector<int>>& dp) {
        if(i<0 && j<0) {return 0;}
        if(i<0) {
            int temp = 0;
            while(j>=0) {
                temp += s2[j];
                j--;
            }
            return temp;
        }
        if(j<0) {
            int temp = 0;
            while(i>=0) {
                temp += s1[i];
                i--;
            }
            return temp;
        }

        if(dp[i][j]!=-1) {return dp[i][j];}

        int donttake = min(s1[i] + solve(s1, s2, i-1, j, dp), s2[j] + solve(s1, s2, i, j-1, dp));
        int take = INT_MAX;
        if(s1[i] == s2[j]) {
            take = solve(s1, s2, i-1, j-1, dp);
        }
        return dp[i][j] = min(donttake, take);
    }

    int minimumDeleteSum(string s1, string s2) {
        // vector<vector<int>> dp(s1.length()+1, vector<int>(s2.length()+1, 0));
        // return solve(s1, s2, s1.length()-1, s2.length()-1, dp);

        vector<int> prev(s2.length()+1);

        for(int j=1;j<=s2.length();j++) {
            prev[j] += s2[j-1]+prev[j-1];
        }
        // for(int i=1;i<=s1.length();i++) {
        //     dp[i][0] += s1[i-1]+dp[i-1][0];
        // }

        for(int i=1;i<=s1.length();i++) {
            vector<int> curr(s2.length()+1);
            curr[0] = s1[i-1]+prev[0];
            for(int j=1;j<=s2.length();j++) {
                int donttake = min(s1[i-1]+prev[j], s2[j-1]+curr[j-1]);
                int take = INT_MAX;
                if(s1[i-1] == s2[j-1]) {
                    take = prev[j-1];
                }

                curr[j] = min(donttake, take);
            }
            prev = curr;
        }
        return prev[s2.length()];
    }
};
16300