C++ 29ms DP solution


  • 4
    Z

    This problem is simiiar to #546 Remove Boxes which uses f[l][r][k] to store the maximum points of range [l, r] with k boxes equal to r. But for this problem, we can use 2D-array DP instead of 3D-array DP because the store of k is useless.

    f[i][j] represents the minumum turns to print the sequence from i to j. The transition function should be:

    f[i][j] = min(f[i][k] + f[k+1][j-1]) for each k where i<k<j and s[k]=s[j]
    

    Do not forget the common transition:

    f[i][j] = f[i][j-1] + 1
    

    And the border condition:

    f[i][j] = 0 where i>j
    

    My C++ code is shown as below(with memorization):

    #include <string>
    #include <cmath>
    
    class Solution
    {
    private:
        int f[100][100];
        
    private:
        int dfs(const std::string& s, int l, int r)
        {
            if (l > r) return 0;
            if (f[l][r]) return f[l][r];
            f[l][r] = dfs(s, l, r - 1) + 1;
            for (int i = l; i < r; ++i)
            {
                if (s[i] == s[r])
                {
                    f[l][r] = std::min(f[l][r], dfs(s, l, i) + dfs(s, i + 1, r - 1));
                }
            }
            return f[l][r];
        }
        
    public:
        int strangePrinter(std::string s)
        {
            memset(f, 0, sizeof(f));
            int len = (int)s.size();
            return dfs(s, 0, len - 1);
        }
    };
    

Log in to reply
 

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