C++ 29ms DP solution

  • 4

    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
        int f[100][100];
        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];
        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.