【 Crampon programming 】LintCode Decoding Encyclopedia —— 1100 Strange printer

author ：BZIClaw

---

1100 Strange printer

Python：

class Solution:
    """ @param s: @return: the minimum number of turns the printer needed in order to print it """
    def strangePrinter(self, s):
        # write your code here
        dp = [[0 for i in range(0,102)] for i in range(0,102)]
        n = len(s)
        if n == 0:
            return 0
        for i in range(0,n):
            dp[i][i] = 1
        for leng in range(1,n):
            for j in range(0,n-leng):
                dp[j][j+leng] = leng + 1
                for k in range(j+1,j+leng+1):
                    temp = dp[j][k-1] + dp[k][j+leng]
                    if s[k-1] == s[j+leng]:
                        temp -= 1
                    dp[j][j+leng] = min(dp[j][j+leng],temp)
        return dp[0][n-1]

Java：

public class Solution {
    
    /** * @param s: * @return: the minimum number of turns the printer needed in order to print it */
    public int strangePrinter(String s) {
    
        // write your code here
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
    
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
    
                if (s.charAt(i) == s.charAt(j)) {
    
                    f[i][j] = f[i][j - 1];
                } else {
    
                    int minn = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
    
                        minn = Math.min(minn, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = minn;
                }
            }
        }
        return f[0][n - 1];
    }
}

C++

class Solution {
    
public:
    /** * @param s: * @return: the minimum number of turns the printer needed in order to print it */
    // Interval class DP
    //DFS
    vector<vector<int>> dp;
    int strangePrinter(string &s) {
    
        // write your code here
        dp = vector<vector<int>>(s.length(), vector<int>(s.length(), -1));
        return strangePrinter(s, 0, s.length() - 1);
    }
    
    int strangePrinter(string &s, int l, int r){
    
        if(l > r)
            return 0;
        if(dp[l][r] != -1)
            return dp[l][r];
        // Default behavior, print s[i] to s[j - 1] and print s[j]
        int ret = strangePrinter(s, l, r - 1) + 1;
        for(int i = l; i < r; i++){
    
            if(s[i] == s[r])
                ret = min(ret, strangePrinter(s, l, i) + strangePrinter(s, i + 1, r - 1));
        }
        return dp[l][r] = ret;
    }
};

JavaScript：

export class Solution {
    

  /** * strangePrinter * * @param s: * @return: the minimum number of turns the printer needed in order to print it */
  strangePrinter(s) {
    
    if ( !s ) {
     return 0; }
    let n = s.length;
    let f = [];
    for (let i = 0; i < n; i++) {
    
        f[i] = [];
        f[i][i] = 1;
    }
    for (let l = 2; l <= n; l++ ) {
    
        for (let i = 0; i + l <= n; i++) {
    
            let j = i + l - 1;
            f[i][j] = 1 + f[i+1][j];
            for (let k = i + 1; k < j; k++) {
    
                if (s[i] == s[k]) {
    
                    f[i][j] = Math.min(f[i][j], f[i+1][k] + f[k+1][j]);
                }
            }
            if (s[i] == s[j]) {
    
                f[i][j] = Math.min(f[i][j], f[i+1][j]);
            }
        }
    }
    return f[0][n-1];
  }

}

Go：None

---

Pay attention to me , Learn more about programming