Single-Sequence DP Problem(单序列动态规划问题)

Usually input is one array or string

Subproblem can be represented as f[i], which represents the best solution ending at position i (f[i]代表包含前i个元素的最优解)

Need to find relationship between f[i] and f[j], where j<i

Usually use array with length n+1 to store the subproblems. Need to initialize f[0], which means the subproblem contains no element.

Palindrome Partitioning II

Analysis:

Subproblems: f[i]: Minimum cuts to form the string ending at position i for palindrome partitioning(前i个字符串最少需要几次cut)
Initialize: f[i] = i-1, at most need i-1 cut to get palindrome partition(初始化过程中f[0]=-1，便于后面计算，因此需要加入特殊情况s.length()=0，return 0)
Function: f[i] = MIN(f[j]+1), j<i && String(j+1~i) is a palindrome
Answer: f[s.length()]

Notice:

Need a helper function to determine if a string is a palindrome. This function also uses dynamic programming!

// Determine if a string is a palindrome
private boolean isPalindrome(String s) {
    if (s.length() == 0 || s.length() == 1)
        return true;

    int M = s.length();
    boolean[][] dp = new boolean[M][M];
    // Initialize
    for (int i=0; i<M; i++) {
        dp[i][i] = true;
    }
    for (int i=0; i<M-1; i++) {
        if (s.charAt(i+1)==s.charAt(i))
            dp[i][i+1]=true;
    }
    // Function:
    // A string is palindrome iff String(1~n-2) is palindrome && char[0]==char[n-1]
    // Need to loop the length first, then start!!!
    for (int length=2; length<M; length++) {
        for (int start=0; length+start<M; start++) {
            dp[start][start+length] = (dp[start+1][start+length-1]
                    &&s.charAt(start)==s.charAt(start+length));
        }
    }
    return dp; 
}

Word Break

Analysis:

Subproblem: f[i]: if the string ending at position i can break into dict(前i个字符是否能被完美分割)
Initialize: f[0]=true, for easiness following subproblems
Function: f[i] = f[j] && String(j~i-1) contained in dict, j<i
Answer: f[s.length()]

Notice:

No need to search all j less than i. Only need to search to the position that (i-j) <= maxLength in dict words.

Therefore, the time complexity is O(NL), where N is the length of the string, L is the length of maxLength word in dict.(If we consider the matching in dict does not take constant time, then O(NL^2)).

    // Utility Function
    // Get the max word length of dict
    private int maxLength(Set<String> dict) {
        int max = 0;
        if (dict == null || dict.size() == 0)
            return max;

        for (String word:dict) {
            max = Math.max(max, word.length());
        }
        return max;
    }

    public boolean wordBreak(String s, Set<String> dict) {

        if (s == null || s.length() == 0)
            return true;
        boolean[] ifBreak = new boolean[s.length()+1];
        int maxWordLength = maxLength(dict);

        // Initialize
        // Actually no need to initialize all i>0 to false
        // Cause Java will automatically initialize
        ifBreak[0] = true;
        for (int i=1; i<ifBreak.length; i++){
            ifBreak[i] = false;
        }

        // Function
        for (int i=1; i<ifBreak.length; i++) {
            for (int j=1; j<=maxWordLength && j<=i; j++) {
                if (!ifBreak[i-j])
                    continue;
                String temp = s.substring(i-j, i);
                if (dict.contains(temp)){
                    ifBreak[i] = true;
                    break;
                }
            }
        }
        // Answer
        return ifBreak[ifBreak.length-1];
    }

Decode Ways

Analysis:

Subproblem: f[i]: number of decode ways with string ending at position i
Initialize: f[0]=1; if s[0] != 0, f[1]=1, else, f[1]=0(if first character is 0, return 0)
Function: if (i-1)*10+i is a valid code, f[i]=f[i-2]+f[i-1],最后两位为单digit情况加上最后两位为双digit情况；else, f[i]=f[i-1],最后两位只能视为单digit的两个字母
Answer: f[s.length()]

Notice:

Need to take care of the situation when 0 occurs.

If s[0]='0', there is no way to decode;
If "10" or "20" occur in string, need to bind two digits together;
When a number>2 occurs before 0, no way to decode.

See the following code how to deal with all these situations:

  for (int i=2; i<=s.length(); i++) {
  // Array elements are initialize to zero
  // If situation like "90" occurs, f[i]=0
  // When two consecutive zero occurs in f[]
  // final result will be zero
            if (s.charAt(i-1)-'0' > 0)
                num[i] = num[i-1];
            int sum = (s.charAt(i-2)-'0')*10 + s.charAt(i-1)-'0';
            if (sum>=10 && sum<=26)
                num[i] += num[i-2];
        }

Single-Sequence DP Problem