House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Refer from House Robber I
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

My Thinkings:

The only difference is it's a circle now instead of a straight line. The last one cant be robbed if the first one has been robbed. If I am going to use the same Dynamic Programming Process, maintaining an array to store current optimized robbery status, I can tell if the first house has been robbed or not from if(opt[1] == 0). However, I cant control the robber not to rob house 1 since opt[1] will always equal to the value in the first house.

That seems to stop me from considering it a DP process. Then I came up with a more mathematics thought-- each time spin the house value by one step, calling DP solution on each new array. Now, I realize how stupid I am. In this way, I still didn't solve the circling thing-- how to include both cases, with the first robbed and with the first one save. And since every house is in a circle, it really doesn't matter where is the starting point if your algorithm is a correct one.

Then I turned to DFS. Since a lot of DP problem can be rewrote in a cached DFS(memorized DFS). It took me some time and finally I gave up this idea since I dont know what to cache.

The final result is easy. It is always like that. I realize I just need to change the initial condition and  run DP twice.

 public class Solution {  
   public int rob(int[] nums) {  
     return Math.max(circle_rob(nums, true), circle_rob(nums, false));  
   }  
     
   private int circle_rob(int[] nums, boolean robFirst){  
     // edge case  
     if(nums == null || nums.length == 0) return 0;  
       
     int[] opt = new int[nums.length+1];  
       
     // initial condition  
     opt[0] = 0;  
     opt[1] = robFirst?nums[0]:0;  
       
     // iteration  
     for(int i = 2;i < opt.length;i++){  
       if(i!=opt.length-1){   
         // normal case  
         opt[i] = Math.max(opt[i-2] + nums[i-1], opt[i-1]);  
       }else{  
         // last robbery  
         opt[i] = robFirst?opt[i-1]:Math.max(opt[i-2]+nums[i-1],opt[i-1]);  
       }  
     }  
       
     return opt[opt.length-1];  
   
   }  
     
     
 }  

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Naive Thinking: First thought was to use DP. The logic is as follows:
opt[i] // the maximum amount of money one rob without alerting the police.
// base case
opt[0] = 0
opt[1] = num[0]
// iteration
opt[i] = max(opt[i-1], opt[i-2]+num[i-1])

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     int opt[] = new int[num.length+1];  
     // base case  
     opt[0] = 0;  
     opt[1] = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++)  
       opt[i] = Math.max(opt[i-1], opt[i-2] + num[i-1]);  
     return opt[num.length];  
   }  
 }  

From the structure of the code. It is easy to see the O(N) space could be constrained to O(1).

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     // base case  
     int pre = 0;  
     int cur = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++){  
       int temp = cur;  
       cur = Math.max(cur, pre + num[i-1]);  
       pre = temp;  
     }  
     return cur;  
   }  
 }  

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Naive Way: A DP approach should be able to conquer this problem. The basic logic is

opt[i] // # of distinct ways to reach top
// base case
opt[0] = 1, opt[1] = 1 (edge case should be n=0, return 0)
// iteration
opt[i] = opt[i-1]+opt[i-2]

 public class Solution {  
   public int climbStairs(int n) {  
     // DP  
     // edge case  
     if(n == 0) return 0;  
     int opt[] = new int[n+1];  
     // base case  
     opt[0] = 1;  
     opt[1] = 1;  
     // iteration  
     for(int i = 2;i <= n;i++) opt[i] = opt[i-1]+opt[i-2];  
     return opt[n];  
   }  
 }  

It turns out this follows Fibonacci Sequence. So there is a famous DFS recursive method. Could use path memorizing to reduce time complexity from O(2^n) to O(n).

 public class Solution {  
   public int climbStairs(int n) {  
     // DFS  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map.put(0,1);  
     map.put(1,1);  
     return dfs(n, map);  
   }  
   private int dfs(int n, Map<Integer, Integer> map){  
     // fast ending  
     if(map.containsKey(n)) return map.get(n);  
     // recursion  
     int rslt = dfs(n-1, map) + dfs(n-2, map);  
     map.put(n, rslt);  
     return rslt;  
   }  
 }  

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Naive Way:  Given word-break has both DP and DFS solutions. I think this question can also be solved by both methods.

First thinking about DP.
Once I got the 1D array denoting whether S[0...i] can be reconstructed by words in dict. After knowing that s[0...i] is re-constructable, need to search for next opt[j] = true (j>i) and dict.contains(s.substring(i,j+1)) = true. A recursive method will be helpful.

This backtrace method didn't get accepted by OJ for TLE. The time consuming for the largest case is really huge. But we still has another backtrace method-> starting from behind rather than starting from beginning.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     List<String> rslt = new ArrayList<String>();  
     // edge case   
     if(s==null || s.length()==0) return rslt;   
     // DP   
     boolean opt[] = new boolean[s.length()+1];   
     // base case   
     opt[0] = true;   
     // iteration   
     for(int i = 1;i <= s.length();i++)   
       for(int t = 0;t < i;t++)   
         opt[i] = opt[i] || opt[t] && dict.contains(s.substring(t,i));   
     backtrace(s, opt, 0, dict, new String(), rslt);  
     return rslt;  
   }  
   private void backtrace(String s, boolean[] opt, int index, Set<String> dict, String path, List<String> rslt){  
     // base case  
     if(index == s.length()){  
       rslt.add(path);  
       return;  
     }  
     // recursion  
     StringBuilder str = new StringBuilder();  
     for(int i = index+1; i < opt.length; i++){  
       str.append(s.charAt(i-1));  
       if(opt[i] && dict.contains(str.toString())){  
         String cur = new String(path);  
         cur += path.length()==0?"":" ";  
         cur += str.toString();  
         backtrace(s, opt, i, dict, cur, rslt);  
       }  
     }  
     return;  
   }  
 }  

This starting from end backtrace method get accepted. Why starting from begin have such a difference from starting from end? What I recall from my Algorithm Course is that Michael taught a starting from end backtrace method when backtracing DP. It is because when starting from begin, some middle result, say opt[4] may be true, while starting from 4, no valid result can be generated. We'll waste a lot of time on invalid final result but valid middle result paths. However, starting from end ensures that each path you travel will be a valid path.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     List<String> rslt = new ArrayList<String>();  
     // edge case   
     if(s==null || s.length()==0) return rslt;   
     // DP   
     boolean opt[] = new boolean[s.length()+1];   
     // base case   
     opt[0] = true;   
     // iteration   
     for(int i = 1;i <= s.length();i++)   
       for(int t = 0;t < i;t++)   
         opt[i] = opt[i] || opt[t] && dict.contains(s.substring(t,i));   
     backtrace(s, opt, s.length(), dict, new Stack<String>(), rslt);  
     return rslt;  
   }  
   private void backtrace(String s, boolean[] opt, int index, Set<String> dict, Stack<String> path, List<String> rslt){  
     // base case  
     if(index == 0){  
       List<String> list = new ArrayList<String>();  
       StringBuilder str = new StringBuilder();  
       list.addAll(path);  
       for(int i = list.size()-1;i>=0;i--){  
         str.append(list.get(i));  
         if(i!=0) str.append(" ");  
       }  
       rslt.add(str.toString());  
       return;  
     }  
     // recursion  
     StringBuilder str = new StringBuilder();  
     int i = index-1;  
     while(i >= 0){  
       String t = s.substring(i,index);  
       if(opt[i] && dict.contains(t)){  
         path.push(t);  
         backtrace(s, opt, i, dict, path, rslt);  
         path.pop();  
       }  
       i--;  
     }  
     return;  
   }  
 }  

For DFS method, I think the path can be constructed on the fly. Also, doing it from end to start.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     List<String> rslt= new ArrayList<String>();  
     // DFS  
     dfs(s, s.length(), dict, new Stack<String>(), rslt);  
     return rslt;  
   }  
   private void dfs(String s, int index, Set<String> dict, Stack<String> path, List<String> rslt){  
     // base case  
     if(index == 0){  
       List<String> list = new ArrayList<String>();  
       StringBuilder str= new StringBuilder();  
       list.addAll(path);  
       for(int i = list.size()-1;i>=0;i--){  
         str.append(list.get(i));  
         if(i!=0) str.append(" ");  
       }  
       rslt.add(str.toString());  
     }  
     // recursion  
     int i = index-1;  
     while(i >= 0){  
       String t = s.substring(i,index);  
       if(dict.contains(t)){  
         path.push(t);  
         dfs(s, i, dict, path, rslt);  
         path.pop();  
       }  
       i--;  
     }  
     return;  
   }  
 }  

It turns out to be the same backtrace method without using DP to generate true or false array. That's nothing weird, it means knowing whether S[0....i] is re-constructable helps little in these test cases. However, that should not be the case, the DP array should be able to provide useful information and deny each path that leads to invalid result. My explanation is the test case for OJ is too weak in Word Break II.

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

Naive Way: Another problem with a dictionary. Since the dictionary is usually large, it's better to do something on the string and left the dictionary to perform dict.contains() function. I came up with a DFS way to cut s and check for the existence of each cut.

DFS first fails for TLE, and then I add a Set to memorize failed index to reduce from O(2^n) to  O(n^2) in run time. This idea is learned from mahdy on his post in Decode Ways

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     // DFS  
     Set<Integer> set = new HashSet<Integer>();  
     return dfs(s, 0, dict, set);  
   }  
   private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){  
     // base case  
     if(index == s.length()) return true;  
     // check memory  
     if(set.contains(index)) return false;  
     // recursion  
     for(int i = index+1;i <= s.length();i++){  
       String t = s.substring(index, i);  
       if(dict.contains(t))  
         if(dfs(s, i, dict, set))  
           return true;  
         else  
           set.add(i);  
     }  
     set.add(index);  
     return false;  
   }  
 }  

And after a fail test, I found out that each string in the dictionary can be used unlimited times. Which leads a DFS without back trace. If each string in the dictionary can be used only once, a simple modification will solve it.

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     // DFS  
     Set<Integer> set = new HashSet<Integer>();  
     return dfs(s, 0, dict, set);  
   }  
   private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){  
     // base case  
     if(index == s.length()) return true;  
     // check memory  
     if(set.contains(index)) return false;  
     // recursion  
     for(int i = index+1;i <= s.length();i++){  
       String t = s.substring(index, i);  
       if(dict.contains(t)){  
         dict.remove(t);  
         if(dfs(s, i, dict, set))  
           return true;  
         else  
           set.add(i);  
         dict.add(t);  
       }  
     }  
     set.add(index);  
     return false;  
   }  
 }  

But what's the general approach? If it is not for path memorizing, DFS will fail in run time.There should exists a totally different solution that aims to solve this problem.

I am thinking about DP. Because in Decode Ways, the formal method was DP while a DFS with path memorize can deal with it, too.
the basic logic will be
opt[i] // whether s[0....i] can be formed by words in dict
// base case
opt[0] = true
// iteration
opt[i] = opt[t] && dict.contains(s.substring(t+1,i)) for 0<t<i

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     // edge case  
     if(s==null || s.length()==0) return dict.contains("");  
     // DP  
     boolean opt[] = new boolean[s.length()+1];  
     // base case  
     opt[0] = true;  
     // iteration  
     for(int i = 1;i <= s.length();i++)  
       for(int t = 0;t < i;t++)  
         opt[i] = opt[i] || opt[t] && dict.contains(s.substring(t,i));  
     return opt[s.length()];  
   }  
 }  

Best Time to Buy and Sell Stock IV

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way: As shown in best-time-to-buy-and-sell-stock-iii. There exists a DP solution within O(nk) run time and space.

The basic logic is
opt[i, j] // the maximum profit using i transactions in j days
// base case
opt[0, j] = 0 for all j
opt[i, 0] = 0 for all i
// iteration
opt[i, j] = max(opt[i, j-1], opt[i-1,t] + p[j] - p[t+1]) for 0<=t < j

However, this algorithm using gets TLE.

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     // edge case  
     if(k > prices.length/2) k= prices.length/2;
     if(prices.length==0) return 0;  
     // DP  
     int opt[][] = new int[k+1][prices.length+1];  
     // base case  
     for(int i = 0;i <= k;i++) opt[i][0] = 0;  
     for(int j = 0;j <= prices.length;j++) opt[0][j] = 0;  
     // iteration  
     for(int i = 1;i <= k;i++){  
       int t = opt[i-1][0] - prices[0];  
       for(int j = 1;j <= prices.length;j++){  
         opt[i][j] = Math.max(opt[i][j-1], t + prices[j-1]);  
         if(j < prices.length) t = Math.max(t, opt[i-1][j] - prices[j]);  
       }  
     }  
     return opt[k][prices.length];  
   }  
 }  

I don't know why this gets TLE, because this is already a high-efficiency algorithm. I saw the Discuss, some one put forward a great idea adding optimization for it. It is when k >= prices.length/2, that means we can make as many transactions as we can, that brings us the problem back to best-time-to-buy-and-sell-stock-ii which can be simply solve in O(n) using a greedy approach. That helps narrow down a lot of tests case to O(n) run time.

 public class Solution {  
   public int maxProfit(int k, int[] prices) {  
     // edge case  
     if(k > prices.length/2){  
       int sum = 0;  
       for(int i = 1;i < prices.length;i++)  
         sum += Math.max(prices[i] - prices[i-1],0);  
       return sum;  
     }  
     if(prices.length==0) return 0;  
     // DP  
     int opt[][] = new int[k+1][prices.length+1];  
     // base case  
     for(int i = 0;i <= k;i++) opt[i][0] = 0;  
     for(int j = 0;j <= prices.length;j++) opt[0][j] = 0;  
     // iteration  
     for(int i = 1;i <= k;i++){  
       int t = opt[i-1][0] - prices[0];  
       for(int j = 1;j <= prices.length;j++){  
         opt[i][j] = Math.max(opt[i][j-1], t + prices[j-1]);  
         if(j < prices.length) t = Math.max(t, opt[i-1][j] - prices[j]);  
       }  
     }  
     return opt[k][prices.length];  
   }  
 }  

Improved Way: Is there a solution better than O(kn)? There is a post using O(n+klogn) run time and O(n) space. It's idea is first find all useful valley-peak pairs and then merge them into k pairs.

https://oj.leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.


Naive Way: I first came up with DFS, which get TLE. By expanding the DFS approach, I see redundancy lies in the reuse of high index calls, like (S, 4) will be called 4 times in example "1224".
So there should be a corresponding DP approach.

 public class Solution {  
   public int numDecodings(String s) {  
     return dfs(s, 0);  
   }  
   private int dfs(String s, int index){  
     // base case  
     if(index >= s.length()) return 1;  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2);  
     if(s.charAt(index) != '0')  
       count += dfs(s, index+1);  
     return count;  
   }  
 }  

The logic of DP can be concluded as
opt[i,j] // the # of ways to decode string s[i....j]
// base case
opt[0,0] = 1 , opt[i,j] = 0 for i > j
// iteration
opt[i,j] = s[j]!='0' ?opt[i,j-1]:0 + (s[j-1] == '1' || s[j-1] == '2' && s[j] <= '6')?opt[i,j-2]:0;

The below is the implementation, time complexity O(n^2) and space O(n^2) required.

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int opt[][] = new int[s.length()][s.length()+1];  
     // base case  
     opt[0][0] = 1;  
     // iteration  
     for(int i = 1;i <= s.length();i++)  
       for(int j = 0;j+i <= s.length();j++)  
         opt[j][j+i] = ((s.charAt(j+i-1)!='0')?opt[j][j+i-1]:0) + ((i >=2 && (s.charAt(j+i-2)=='1' || s.charAt(j+i-2)=='2' && s.charAt(j+i-1)<='6'))?opt[j][j+i-2]:0);  
     return opt[0][s.length()];  
   }  
 }  

In the above code, I found out that the step is totally useless, opt[3][4] will never be used to compute opt[0][4]. So the final solution should be O(n) time and space.

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int opt[] = new int[s.length()+1];  
     // base case  
     opt[0] = 1;  
     // iteration  
     for(int j = 1;j <= s.length();j++)  
       opt[j] = ((s.charAt(j-1)!='0')?opt[j-1]:0) + ((j >=2 && (s.charAt(j-2)=='1' || s.charAt(j-2)=='2' && s.charAt(j-1)<='6'))?opt[j-2]:0);  
     return opt[s.length()];  
   }  
 }  

It's really bad to write an algorithm without carefully think about dimension. The problem is a one -dimension problem, while the middle result may be useful. But in writing the algorithm on can clearly see that middle result is useless.

Improved Way: As usual, a 2D space can always be reduced to 1D when current result only rely on previous row/column. For this problem, current result only relies on previous two steps. We can reduced the space use to O(1).

 public class Solution {  
   public int numDecodings(String s) {  
     // edge case  
     if(s.length()==0) return 0;  
     // DP  
     int father = 1, grandpa = 1;  
     // base case  
     int opt = 1;  
     // iteration  
     for(int j = 1;j <= s.length();j++){  
       opt = ((s.charAt(j-1)!='0')?father:0) + ((j >=2 && (s.charAt(j-2)=='1' || s.charAt(j-2)=='2' && s.charAt(j-1)<='6'))?grandpa:0);  
       grandpa = father;  
       father = opt;  
     }  
     return opt;  
   }  
 }  

While, it's not the end, I finally find someone's post with an improved DFS approach. It's from mahdy,
he uses a map to store each path that has been visited. Each time we make the recursive call, visit the map first. That really brings the run time from O(2^n) to O(n)!

I'll just modify on my previous DFS code.

 public int numDecodings(String s) {  
     if(s == null || s.length() == 0) return 0;  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map. put(s.length(), 1);  
     return dfs(s, 0, map);  
   }  
   private int dfs(String s, int index, Map<Integer, Integer> map){  
     // check path memory  
     if(map.containsKey(index)) return map.get(index);  
     // recursion  
     int count = 0;  
     if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))  
       count += dfs(s, index+2, map);  
     if(s.charAt(index) != 0)  
       count += dfs(s, index+1, map);  
     map.put(index, count);  
     return count;  
   }  

Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true 

Naive Way:  Cam up with DP idea at first glance. Should not be a complicated logic.

opt[i][j] // represents whether S[0....i] matches P[0...j] or not
// base case
opt[0][0] = true;
opt[0][j] = true; if consecutive '.*' or 'x*' are met.
// iteration
opt[i][j] =
if(s[i]==p[j] || p[j] == '.') opt[i-1][j-1]
if(p[j] == '*')
    if(s[i] == p[j-1] || p[j-1] == '.')
        opt[i][j-2]  // don't take s[i] to match p[j-1],p[j]
        || opt[i-1][j] // take s[i] to match p[j-1],p[j]
    else
        opt[i][j-2] // cannot take s[i] to match p[j-1],p[j]

This algorithm is O(nm) run time and space. Can be reduced to O(m) since current column is affected only by previous column.

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     // DP  
     boolean opt[][] = new boolean[s.length()+1][p.length()+1];  
     // base case  
     opt[0][0] = true;  
     boolean valid = false;  
     for(int j = 2;j <= p.length();j+=2){  
       if(p.charAt(j-1)=='*'){ valid = true; opt[0][j] = true;}  
       else{ valid = false;}  
       if(!valid) break;  
     }  
     // iteration  
     for(int i = 1;i <= s.length();i++){  
       for(int j = 1;j <= p.length();j++){  
         opt[i][j] = false;  
         if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.') opt[i][j] = opt[i-1][j-1];  
         else if(p.charAt(j-1)=='*'){  
           if(s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')  
             opt[i][j] = opt[i-1][j] || opt[i][j-2];  
           else  
             opt[i][j] = opt[i][j-2];  
         }  
       }  
     }  
     return opt[s.length()][p.length()];  
   }  
 }  

Below is a O(n) space version. Could use only one array, but two arrays is more clear.

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     // DP  
     boolean opt[] = new boolean[p.length()+1];  
     boolean pre[] = new boolean[p.length()+1];  
     // base case  
     pre[0] = true;  
     boolean valid = false;  
     for(int j = 2;j <= p.length();j+=2){  
       if(p.charAt(j-1)=='*'){ valid = true; pre[j] = true;}  
       else{ valid = false;}  
       if(!valid) break;  
     }  
     // iteration  
     for(int i = 1;i <= s.length();i++){  
       for(int j = 1;j <= p.length();j++){  
         opt[j] = false;  
         if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.') opt[j] = pre[j-1];  
         else if(p.charAt(j-1)=='*'){  
           if(s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')  
             opt[j] = pre[j] || opt[j-2];  
           else  
             opt[j] = opt[j-2];  
         }  
       }  
       for(int j = 0;j <= p.length();j++)  
         pre[j] = opt[j];  
     }  
     return pre[p.length()];  
   }  
 }  

There is also a DFS version in Discuss. But the time complexity as far as I am concerned is O(2^n). However the OJ seems just listing as many complicated test cases as possible without large size test cases.

A DFS with path memorizing is as follows.

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     Map<List<Integer>, Boolean> map = new HashMap<List<Integer>, Boolean>();  
     for(int i = p.length();i>=0;i-=2){  
       if(i==p.length() || i < p.length()-1 && p.charAt(i+1)=='*'){  
         List<Integer> list = new ArrayList<Integer>();  
         list.add(s.length());  
         list.add(i);  
         map.put(list, true);  
       }else  
         break;  
     }  
     return isMatch(s.toCharArray(), 0, p.toCharArray(), 0, map);  
   }  
   private boolean isMatch(char[] s, int i, char[] p, int j, Map<List<Integer>, Boolean> map){  
     // check memory  
     List<Integer> list = new ArrayList<Integer>();  
     list.add(i);  
     list.add(j);  
     if(map.containsKey(list)) return map.get(list);  
     // ending case  
     if(i < 0 || j < 0 || j >= p.length) return false;  
     // recursion  
     if(p[j] == '*'){  
       int u = i-2;  
       while(u < s.length && (u==i-2 || s[u] == p[j-1] || p[j-1] == '.'))  
         if(isMatch(s, ++u, p, j+1, map)){   
           map.put(list, true);  
           return true;  
         }  
     }  
     else if(i < s.length && (s[i] == p[j] || p[j] == '.')) return isMatch(s, i+1, p, j+1, map);  
     else if(j+1 < p.length && p[j+1] == '*') return isMatch(s, i, p, j+2, map);  
     map.put(list, false);  
     return false;  
   }  
 }  

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3 

Naive Way: I just came up with an idea that is similar to what I did in  Unique Binary Search Trees II.
The idea is to use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. The total number of distinct structure is their product. Thus, sum up the product for all numbers.

A recursive solution popped up.

 public class Solution {  
   public int numTrees(int n) {  
     // base case  
     if(n <= 1){return 1;}  
     // recursion  
     int sum = 0;  
     for(int i = 1;i <= n;i++)  
       sum += numTrees(i-1-0) * numTrees(n-i);  
     return sum;  
   }  
 }  

Use path memorize can reduce the run time from O(2^n) to O(n^2).

 public class Solution {  
   public int numTrees(int n) {  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map.put(0,1);  
     map.put(1,1);  
     return numTrees(n, map);  
   }  
   private int numTrees(int n, Map<Integer, Integer> map){  
     // check memory  
     if(map.containsKey(n)) return map.get(n);  
     // recursion  
     int sum = 0;  
     for(int i = 1;i <= n;i++)  
       sum += numTrees(i-1, map) * numTrees(n-i, map);  
     map.put(n, sum);  
     return sum;  
   }  
 }  

Improved Way: In the Discuss, I saw somebody using DP, which is quite similar to the above. It is written by liaison from leetcode.

 public int numTrees(int n) {  
   int [] G = new int[n+1];  
   G[0] = G[1] = 1;  
   for(int i=2; i<=n; ++i) {  
     for(int j=1; j<=i; ++j) {  
       G[i] += G[j-1] * G[i-j];  
     }  
   }  
   return G[n];  
 }  

Also, somebody raise up that this problem follows the Catalan Number. Can use Catalan formula to generate the number.

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

Naive Way: I came up with DP at the first glance. However, it is hard to write the iteration logic. I decide to put DP away. I turned to a DFS solution which follows a brute force idea. I am sure it works to solve the problem but didn't get passed by OJ. The run time is O(2^n).

 public class Solution {  
   private int sum;  
   public int numDistinct(String S, String T) {  
     sum = 0;  
     dfs(S,T,0,0);  
     return sum;  
   }  
   private void dfs(String S, String T, int i, int j){  
     // end case  
     if(i >= S.length() || j >= T.length()) return;  
     // recursion  
     for(int u = i;u < S.length();u++){  
       if(S.charAt(u) == T.charAt(j)){  
         if(j==T.length()-1) sum++;  
         dfs(S,T,u+1,j+1);  
       }  
     }  
   }  
 }  

Then I turn back to DP. Even though it's hard to figure out how the iteration logic works, I cannot think of other ways. So I stick to DP. I didn't work out the logic, but I work out the code for the logic using listing-> find pattern method. I listed many cases for opt[i][j] with its three highly related opt[i-1][j], opt[i-1][j-1], opt[i][j-1]. I know opt[i][j] is gonna come out from these three sub opts. After finally figure out opt[i][j] = opt[i-1][j] + opt[i-1][j-1] when S[i]==T[j], I turn back to think how the inner logic is. It is as follows:

When S[i] != T[j], we know that opt[i][j] = opt[i-1][j]! Simple but hard to come up with. Just think that since S[i]!=T[j], S[i] is useless in covering T[0....j].

When S[i] == T[j], S[i] matched T[j]! That brings us to if S[0....i-1] and T[0...j-1] are matched pair, S[0...i] and T[0...j] are matched pairs, too. And the value will be kept. Thus, when S[i] == T[j],
opt[i][j] = opt[i-1][j] + opt[i-1][j-1].

The algorithm took O(nm) run time and space.

 public class Solution {  
   public int numDistinct(String S, String T) {  
     // DP  
     int opt[][] = new int[S.length()+1][T.length()+1];  
     // base case  
     for(int i = 0;i <= S.length();i++) opt[i][0] = 1;  
     // iteration  
     for(int i = 1;i <= S.length();i++)  
       for(int j = 1;j <= T.length();j++)  
         opt[i][j] = opt[i-1][j] + (S.charAt(i-1)== T.charAt(j-1)?opt[i-1][j-1]:0);  
     return opt[S.length()][T.length()];  
   }  
 }  

Improved Way: As usual, once the original version of a 2D space DP came out, there is always a way to convert 2D matrix to 1D array once the logic doesn't affect previous rows.

 public class Solution {  
   public int numDistinct(String S, String T) {  
     // DP  
     int opt[] = new int[T.length()+1];  
     // iteration  
     for(int i = 1;i <= S.length();i++){  
       int pre = 1;  
       for(int j = 1;j <= T.length();j++){  
         int temp = opt[j];  
         opt[j] = opt[j] + (S.charAt(i-1)== T.charAt(j-1)?pre:0);  
         pre = temp;  
       }  
     }  
     return opt[T.length()];  
   }  
 }  

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character


Naive Way:这道题应该是DP教学题目，还是挺难的。
基本逻辑为
opt[i][j] // minimum steps to convert word1[0...i] to word2[0...j]
// base case
opt[0][j] = j, opt[i][0] = i; for all i,j
// iteration
opt[i][i] = min(opt[i-1][j] + 1, opt[i][j-1] + 1, opt[i-1][j-1]+(word1[i]==word[j]?0:1));
这个min里对应的三种情况分别是                 insert word1     insert word2               replace a character

大概是之前做过一遍吧，这次想这个逻辑想的特别转，一次通过了。

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int opt[][] = new int[word1.length()+1][word2.length()+1];  
     // base case  
     for(int i = 0;i <= word1.length();i++) opt[i][0] = i;  
     for(int j = 0;j <= word2.length();j++) opt[0][j] = j;  
     // iteration  
     for(int i = 1;i <= word1.length();i++)  
       for(int j = 1;j <= word2.length();j++)  
         opt[i][j] = Math.min(Math.min(opt[i-1][j]+1,opt[i][j-1]+1),opt[i-1][j-1] + (word1.charAt(i-1)==word2.charAt(j-1)?0:1));  
     return opt[word1.length()][word2.length()];  
   }  
 }  

Improved Way:提高DP的方法，我觉得一是看能不能消去一层循环（时间上），而是看能不能用少一维的空间（空间上）。这道题时间上应该就是这样了，空间貌似值得推敲。

自习琢磨一番，将2D的空间变成1D的。

 public class Solution {  
   public int minDistance(String word1, String word2) {  
     int opt[] = new int[word2.length()+1];  
     // base case  
     for(int j = 0;j <= word2.length();j++) opt[j] = j;  
     // iteration  
     for(int i = 1;i <= word1.length();i++){  
       int pre = i, corner = i-1;  
       for(int j = 1;j <= word2.length();j++){  
         int temp = corner;  
         corner = opt[j];  
         temp += (word1.charAt(i-1)==word2.charAt(j-1)?0:1);   
         opt[j] = Math.min(temp,Math.min(opt[j],pre)+1);  
         pre = opt[j];  
       }  
       opt[word2.length()] = pre;  
     }  
     return opt[word2.length()];  
   }  
 }   

Unique Paths II

Unique Paths II

 

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.
Note: m and n will be at most 100.

Naive Way: 在算法上修改。这是Unique Path 的算法。

public class Solution {
    public int uniquePaths(int m, int n) {
        int opt[][] = new int[m][n];
        // base case
        for(int i = 0;i < m;i++) opt[i][0] = 1;
        for(int j = 0;j < n;j++) opt[0][j] = 1;
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = opt[i-1][j] + opt[i][j-1];
        return opt[m-1][n-1];
    }
}


如果当前有障碍物，那么就要置0，所以新逻辑是
opt[i][0] = matrix[i][0] ==0?0:opt[i-1][0];
opt[0][j] = matrix[0][j]==0?0:opt[0][j-1];
opt[i][j] = matrix[i][j]==0?0:opt[i-1][j]+opt[i][j-1];

算法复杂度为O(nm), space O(nm)。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        
        int opt[][] = new int[m][n];
        // base case
        opt[0][0] = obstacleGrid[0][0]==1?0:1;
        for(int i = 1;i < m;i++) opt[i][0] = obstacleGrid[i][0]==1?0:opt[i-1][0];
        for(int j = 1;j < n;j++) opt[0][j] = obstacleGrid[0][j]==1?0:opt[0][j-1];
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = obstacleGrid[i][j]==1?0:(opt[i-1][j] + opt[i][j-1]);
        return opt[m-1][n-1]; 
    }
}

对应的，写出简化space的形式。这里有一点和之前不一样是i=0也要写进循环，它对应单一一行的情况，因为之前没有障碍，一行就是1，现在还要判断一下是否有障碍，

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = obstacleGrid[i][0]==1?0:(i==0?1:row[i-1]);
        // iteration
        for(int j = 1;j < n;j++)
            for(int i = 0;i < m;i++)
                row[i] = obstacleGrid[i][j]==1?0:((i==0 || obstacleGrid[i-1][j]==1?0:row[i-1]) + (obstacleGrid[i][j-1]==1?0:row[i]));
        return row[m-1]; 
    }
}

附上之前的代码方便对照：

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m > n) return uniquePaths(n,m);
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        // ieration
        for(int j = 1;j < n;j++)
            for(int i = 1;i < m;i++)
                row[i] = row[i] + row[i-1];
        return row[m-1];
    }
}

还有就是为了达到 O(min(m,n))的space，应该要比较一下n和m，取较小的做数组。


Improved Way: 这道题跟之前有一个很大的不同在于，输入参数有一个m-by-n的数组，如果可以破坏这个数组，就可以利用原来的数组存opt而不需要额外的空间。

space O(1)

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m==0) return 0;
        int n = obstacleGrid[0].length;
        
        // base case
        obstacleGrid[0][0] = obstacleGrid[0][0]==1?0:1;
        for(int i = 1;i < m;i++) obstacleGrid[i][0] = obstacleGrid[i][0]==1?0:obstacleGrid[i-1][0];
        for(int j = 1;j < n;j++) obstacleGrid[0][j] = obstacleGrid[0][j]==1?0:obstacleGrid[0][j-1];
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                obstacleGrid[i][j] = obstacleGrid[i][j]==1?0:(obstacleGrid[i-1][j] + obstacleGrid[i][j-1]);
        return obstacleGrid[m-1][n-1]; 
    }
}

Unique Paths

Unique Paths

 

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


Naive Way: 第一反应是用DP做。
基本逻辑为：
opt(i,j) // # of paths from (0,0) to (i,j)
// base case
opt(i,0)=1 0<=i<m
opt(0,j)=1 0<=j<n
// iteration
opt(i,j) = opt(i-1,j) + opt(i,j-1)


算法复杂度为O(nm), space O(mn)

public class Solution {
    public int uniquePaths(int m, int n) {
        int opt[][] = new int[m][n];
        // base case
        for(int i = 0;i < m;i++) opt[i][0] = 1;
        for(int j = 0;j < n;j++) opt[0][j] = 1;
        // ieration
        for(int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                opt[i][j] = opt[i-1][j] + opt[i][j-1];
        return opt[m-1][n-1];
    }
}


将2D矩阵用两个1D数组表示可节省空间。space O(m+n)

public class Solution {
    public int uniquePaths(int m, int n) {
        int row[] = new int[m];
        int col[] = new int[n];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        for(int j = 0;j < n;j++) col[j] = 1;
        // ieration
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                row[i] += col[j];
                col[j] = row[i];
            }
        }
        return row[m-1];
    }
}


Improved Way: Discuss里有两种更好的方法，一种是对两个1D数组的再做简化。
因为从上一格到下一格只有一条路，下一格其实并不需要额外记录，只需用上一格的数据就可以，所以一旦上一层的前一格记录好了，当前层的前一个也就记录好了，因为二者是一样的。只需要对每一层做row[i] = row[i] + row[i-1]的操作了。

space 是 O(min(m,n))

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m > n) return uniquePaths(n,m);
        int row[] = new int[m];
        // base case
        for(int i = 0;i < m;i++) row[i] = 1;
        // ieration
        for(int j = 1;j < n;j++)
            for(int i = 1;i < m;i++)
                row[i] += row[i-1];
        return row[m-1];
    }
}


还有一个方法是 这个问题和杨辉三角 是一样的，可以构建一格杨辉三角取对应位置的值。这里等我做了杨辉三角再补充。

Maximal Rectangle

Maximal Rectangle

 

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 

Naive Way: brute force的方法，对每一个点都遍历O(n^2)求出最大的长方形，算法复杂度是O(n^3)。由于有了Largest Rectangle in Histogram 的解法是O(n)，可以把矩阵从上到下扫一遍，得到n组Histogram的数据，每一组用上面的方法算最大rectangle，就可以实现O(n^2)的算法复杂度。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        if(matrix.length==0){return max;}
        int height[] = new int[matrix[0].length];
        for(int i = 0;i < matrix.length;i++){
            for(int j = 0;j < matrix[i].length;j++){
                int t = height[j]==0?0:height[j]-1;
                while(i+t < matrix.length && matrix[i+t][j]=='1') t++;
                height[j] = t;
            }
            max = Math.max(max,largestRectangleArea(height));
        }
        return max;
    }
    
    public int largestRectangleArea(int[] height) {
        int largest = 0;
        int i;
        Stack<Integer> stack = new Stack<Integer>();
        // forward
        i = 0;
        while(i < height.length){
            if(!stack.isEmpty() && height[i] < height[stack.peek()])
                largest = Math.max(largest, height[stack.pop()]*(i-(stack.isEmpty()?-1:stack.peek())-1));
            else
                stack.push(i++);
        }
        // backward
        while(!stack.isEmpty()){
            largest = Math.max(largest, height[stack.pop()] * (i-(stack.isEmpty()?-1:stack.peek())-1));
        }
        return largest;
    }
}

 

 

Improved Way: 这样做法算是比较普遍的做法。在Discuss里还有一种DP的做法，也是O(n^2)，颇受好评。https://oj.leetcode.com/discuss/20240/share-my-dp-solution

 

基本逻辑为：

left[i][j] // the left most position with '1' in row i connected with position[i][j]

right[i][j] // the right most position with '1' in row i connected with position[i][j] 

height[i][j] // current height in column j for position[i][j]

 

left[i][j] = matrix[i][j] =='1'? max(leftMostZeroPosition, left[i-1][j]): 0;

right[i][j] = matrix[i][j] =='1'?min(rightMostZeroPosition, right[i-1][j]):0;

height[i][j] = matrix[i][j] =='1'?height[i-1][j]+1:0;

area[i][j] = height[i][j] *( right[i][j] - left[i][j]);

所有2D array都可以用1D array表示。

 

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int max = 0;
        int n = matrix.length;
        if(n==0){return max;}
        int m = matrix[0].length;
        int h[] = new int[m];
        int l[] = new int[m];
        int r[] = new int[m];
        Arrays.fill(r, m);
        for(int i = 0;i < n;i++){
            int curLeft = 0, curRight = m;
            for(int j = 0;j < m;j++){
                l[j] = matrix[i][j]=='1'?Math.max(curLeft,l[j]):0;
                curLeft = matrix[i][j]=='1'?curLeft:j+1;
                
                r[m-1-j] = matrix[i][m-1-j]=='1'?Math.min(curRight,r[m-1-j]):m;
                curRight = matrix[i][m-1-j]=='1'?curRight:m-1-j;
                
                h[j] = matrix[i][j] =='1'?h[j]+1:0;
            }
            
            for(int j = 0;j < m;j++)
                max = Math.max(max, h[j] * (r[j]-l[j]));
        }
        return max;
    }
}

 

Math.max(curLeft,l[j]) 这一个逻辑使得当前最右边为1的位置与上一层保持一致性。

 

在GeeksforGeeks上有一个更容易懂的DP的做法，不过是正方形的。

Minimum Path Sum

Minimum Path Sum

 

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Naive Way:第一眼就觉得是DP的题。而且逻辑应该就是取左边和上边来的路径较小的那支。

算法复杂度O(nm), space O(1)，利用原来矩阵存贮中间结果。

public class Solution {
    public int minPathSum(int[][] grid) {
        // DP
        if(grid.length==0){return 0;}
        // base case
        for(int i = 1;i < grid.length;i++)
            grid[i][0] += grid[i-1][0];
        for(int j = 1;j < grid[0].length;j++)
            grid[0][j] += grid[0][j-1];
        // iteration
        for(int i = 1;i < grid.length;i++)
            for(int j = 1;j < grid[0].length;j++)
                grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);
        return grid[grid.length-1][grid[0].length-1];
    }
}

 

Palindrome Partitioning II

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

(注：写的废话有点多，可以直接看我在leetcode discuss的提问https://oj.leetcode.com/discuss/24253/how-to-get-from-o-n-3-to-o-n-2-java-solution-sharing）
Naive Way: 好像有上一题的DP的二维矩阵就可以很快得到最小割了。

基本一致的回溯方式，这样的算法复杂度是O(2^n)，最坏的情况。然后会出现超时。

public class Solution {
    public int minCut(String s) {
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
        
        return search(0,opt,-1);
    }
    
    private int search(int begin, boolean[][] opt, int cut){
        int min = opt[0].length;
        if(begin==opt[0].length-1)
            return cut;
        for(int i = begin+1;i < opt[0].length;i++)
            if(opt[begin][i])
                min = Math.min(search(i,opt,cut+1),min);
        return min;
    }
}


Improved Way:这时我想到O(n)求longest palindrome substring的方法。因为那个方法能在O(n)的时间内求出所有字符的覆盖范围，那么用贪心的思想取覆盖范围大的，就可以实现最小分割数了。

实际做时，发现这种greedy的思想会产生一个bug。当String = aaaba的时候。
0  1  2  3  4  5  6  7  8  9  10
#  a  #  a   #  a  #  b  #  a  #
1  2  3  4  3  2  1  4  1  2  1

先取第一个4就会得到{"aaa","b","a"}
先取第二个4就会得到{"aa","aba"}
一个是3割一个是2割。
这个BUG只会在OJ的倒数第二种测例中出现，很容易忽略。同时，这个例子也可以说明对DP的结果进行遍历时，不能够用greedy的思想去最大长度的找一个max(j-i) 其中 opt[i][j]=true。否则就会出现这里这种先找前3个a而导致后面必须用多一个割的情况。



这时看了一眼这道题的标签，是DP耶。幡然醒悟，应该用一个更直接的DP。
基本逻辑为：
opt(i,j) //表示将String s[i-j]分成全palindrome子串的最少割数。
// base case
opt(i,i) = 0     0<= i < s.length()
// iteration
opt(i,j) =
if s[i]==s[j] && opt(i+1,j-1)==0
     0
else
     min(opt(i,t)+opt(t+1,j)+1)  for  i<= t < j

算法复杂度为O(n^3)，但还是超时了。
public class Solution {
    public int minCut(String s) {
        // DP
        int opt[][] = new int[s.length()][s.length()];
        // base case 0
        // iteration
        for(int i = 1;i < s.length();i++){
            for(int j = 0;j+i < s.length();j++){
                if(s.charAt(j)==s.charAt(j+i) && opt[j+1][j+i-1]==0){
                    opt[j][j+i] = 0;
                }else{
                    opt[j][j+i] = i;
                    for(int t = j;t < j+i;t++)
                        opt[j][j+i] = Math.min(opt[j][j+i], opt[j][t]+opt[t+1][j+i]+1);
                }
            }
        }
        return opt[0][s.length()-1];
    }
}


可以不可以在O(n^2)内完成呢？如果DP只有一个参数呢？
opt[i] // 表示分割s[0-i]所需最小分割数。
 // base case
opt[0] = 0;
// iteration
opt[i] =
if(s[0-i] is palindrome)
     0
else
    min(opt[t] + s[t+1 ~ i] is palindrome?1:i-t)

这样做虽然只有O(n)的外层循环，但是每一次循环都要遍历之前所有还要同时判断当前的是否为palindrome,每一次循环就需要O(n^2)，所以还是O(n^3)。

还是看了一下discuss发现自己好愚蠢，在一开始就已经在O(n^2)的时间内求出所有s[i~j]是否为palindrome了。所以每一层循环现在只需要O(n)的时间，总的时间就是O(n^2)了。


public class Solution {
    public int minCut(String s) {
        // use DP to determine any palindrome substring
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1]; 
        
        
        // use DP to determine min cut
        int cut[] = new int[s.length()+1];
        for(int i = 1;i <= s.length();i++){
            if(opt[0][i])
                cut[i] = 0;
            else{
                cut[i] = i-1;
                for(int t = 1;t < i;t++){
                    cut[i] = Math.min(cut[i],cut[t] + (opt[t][i]?1:i-t));
                }
            }
        }
        return cut[s.length()];
        
    }
}

 

Palindrome Partitioning

Palindrome Partitioning

 

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ] 

Naive Way:第一感觉可以用recursive的方法，对String第一个palindrome及它后面的部分

分别进行recursive call求palindrome partition。具体下来就是：

如果一个String只有一个字符，则返回单个字符的list。

否则，遍历String,一旦遇到palindrome就提取该子串作为头，对后部分分别进行recursive call，

合并两者，加入结果中。 

有一个问题就是如何求包含第一个字母的所有palindrome。在longest palindrome substring中

在O(n)内可以求出以所有字符为中心最大范围的palindrome,当然用在这里肯定也可以求处包含第一个

字符的所有palindrome。当肯定不是最佳的，但是要想找出在小于O(n)的时间内求出包含第一个字符

的所有palindrome，看来是不可能的，所以，干脆就用这个方法了。

这里我用求longest palindrome substring中的方法求出所有包含第一个字符的palindrome的

最后位置，以此方便分割字符。

算法复杂度应该是f(n)+f(n-1)+f(n-2)+... 而f(n)在最坏的情况应该是O(2^n)的，所以最后的

算法复杂度是O(2^n)。不知道这样算对不对，总之是一个很差的算法复杂度。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> gross = new ArrayList<List<String>>();
        List<Integer> num = panlindromeIndex(s);
        for(int i = 0;i < num.size();i++){
            String left = s.substring(0,num.get(i));
            List<List<String>> right = partition(s.substring(num.get(i),s.length()));
            if(right.size()==0){
                List<String> base = new ArrayList<String>();
                base.add(left);
                gross.add(base);
            }
            for(int j = 0;j < right.size();j++){
                right.get(j).add(0,left);
                gross.add(right.get(j));
            }
        }
        return gross;
    }
    
    // return a list of position(i) where [0~i] is a panlindrome
    private List<Integer> panlindromeIndex(String s){
        List<Integer> list = new ArrayList<Integer>();
        s = preProcess(s);
        int p = 0;
        int f[] = new int[s.length()];
        for(int i = 1;i < s.length();i++){
            f[i] = 1;
            if(i < p + f[p]){
                if(p+f[p] - i > f[2*p-i])
                    f[i] = f[2*p-i];
                else
                    f[i] = p+f[p]-i;
            }
            while(i-f[i] >= 0 && i + f[i] < s.length()){
                if(s.charAt(i-f[i])!=s.charAt(i+f[i]))
                    break;
                f[i]++;
            }

            if(i+f[i] > p+f[p]){p=i;}

        }
        for(int i = 1;i < f.length;i+=2){
            if(i-f[i] < 0)
                list.add((i+f[i])/2);
            if(i-1-f[i-1] < 0)
                list.add((i-1+f[i-1])/2);
        }
        return list;
    }
    
    private String preProcess(String s){
        StringBuilder rlst = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            rlst.append('#');
            rlst.append(s.charAt(i));
            if(i==s.length()-1)
                rlst.append('#');
        }
        return rlst.toString();
    }
}

Improved Way:为了提高算法效率，我思考了一下以上算法的缺陷。recursive call里产生

的子字符串很多都是重复的，这里使算法效率降低了很多。有没有办法先把这些有效的子字符串

写好，然后需要的时候直接调用呢？这时我想到了求longest palindrome substring最

原始的方法——DP。DP可以用一个二维矩阵告诉我某一段子字符串是否回文，着就相当于把所有

可能的子字符串都先求出来了，那如何调用呢。DP得到的是一个二维矩阵，通过上一层的某段

是否回文，可以用DFS的方法，遍历下一层对应所有可能的回文子串，这里又是用带回溯的DFS，

就像N-Queen和Sudoku一样。

算法复杂度为O(n^2)。比之前提高了不少。

public class Solution {
    public List<List<String>> partition(String s) {
        // DP
        List<List<String>> gross = new ArrayList<List<String>>();
        Deque<Range> deque = new LinkedList<Range>();
        Stack<Range> stack = new Stack<Range>();
        boolean opt[][] = new boolean[s.length()][s.length()+1];
        // base case
        for(int i = 0;i < s.length();i++){
            opt[i][i+1] = true;
            opt[i][i] = true;
        }
        // iteration
        for(int i = 2;i <= s.length();i++)
            for(int j = 0;j+i <= s.length();j++)
                opt[j][j+i] = s.charAt(j)==s.charAt(j+i-1) && opt[j+1][j+i-1];
        // construct result using DFS
        for(int i = 1;i <= s.length();i++){
            if(opt[0][i]){
                Range range = new Range(0,i);
                stack.push(range);
            }
        }
        while(!stack.isEmpty()){
            Range range = stack.pop();
            deque.offerLast(range);
            boolean hasNext = false;
            if(range.e==s.length()){
                List<String> list = new ArrayList<String>();
                for(int i = 0;i < deque.size();i++){
                    Range next = deque.pollFirst();
                    list.add(s.substring(next.b,next.e));
                    deque.offerLast(next);
                }
                gross.add(list);
            }else{
                for(int i = range.e+1;i <= s.length();i++){
                    if(opt[range.e][i]){
                        Range sub = new Range(range.e,i);
                        stack.push(sub);
                        hasNext = true;
                    }
                }
            }
            // back trace
            if(!hasNext || range.e==s.length()){
                if(!stack.isEmpty()){
                    Range peek = stack.peek();
                    while(!deque.isEmpty()){
                        if(deque.pollLast().b == peek.b)
                            break;
                    }
                }
            }
        }
        return gross;
    }
    

    class Range{
        int b;
        int e;
        Range(int begin, int end){
            b = begin;
            e = end;
        }
    }
} 

看了看自己第一次的做法，发现比这种用DFS遍历的方法高明多了，是根据DP的二维矩阵从后往前

进行遍历的方法。运行时间也是最短的。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> lst = new ArrayList<List<String>>();
        List<String> temp = new ArrayList<String>();
        int len = s.length();
        boolean opt[][] = new boolean[len][len];
        
        // initialize
        for(int i = 0;i < len;i++){Arrays.fill(opt[i], false);}
        for(int i = 0;i < len;i++){opt[i][i] = true;}
        
        // recurrence
        for(int u = 1;u < len;u++){
         for(int i = 0;i+u < len;i++){
          if(u >= 2){
           opt[i][i+u] = (opt[i+1][i+u-1] && s.charAt(i)==s.charAt(i+u));
          }else if(u == 1){
           opt[i][i+u] = s.charAt(i) == s.charAt(i+u)? true:false;
          }
         }
        }
        
        // generate result according to opt
        generateList(0,len,s,opt,temp,lst);

        //show result
        //System.out.print(lst);
        return lst;

    }

 

 private boolean generateList(int i, int len, String s, boolean opt[][], List<String> temp,List<List<String>> lst){
  for(int j = 0;j < len; j ++){
   if(opt[i][j]){
    List<String> newCombo = new ArrayList<String>(temp);
    newCombo.add(s.substring(i, j+1));
    if(j == len-1){
     lst.add(newCombo);
    }else{
     generateList(j+1,len,s,opt,newCombo,lst);
    }
   }
  }
  return true;
 }

} 

突然发现我的算法课老师Michael讲的如何回溯DP得到的矩阵，得到正式的结果的那种从尾到头的方法，其实是一种DFS。 

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

 

 

Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Naive Way: 这道题是课本DP那章的一道原题，我才想起来我当时做过。于是就用DP做了。
基本逻辑为
opt[i] //表示第ii所能获得的最大利润
// base case
opt[0] = 0
// iteration
opt[i] = max(opt[i-1], p[i] - min)

因为不需要内层循环访问之前的opt, 看来O(1)的space就足够了。

public int maxProfit(int[] prices) {
        if(prices.length==0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            opt = Math.max(opt, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return opt;
    }

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

 

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Naive Way:因为在前面已经有了卖一次的代码，可以认为是交易两次和交易一次的比较，交易一次则采用之前的代码，交易两次则将视为将数组切割成两段，对每一段求一次交易的最大值，然后相加，着要求对每一位置作为切割点遍历。这样的算法复杂度是O(n^2)。

public int maxProfit(int[] prices) {
        if(prices.length <= 3){
            return subProfit(prices);
        }
        int max = 0;
        for(int i = 1;i < prices.length-1;i++){
            int sub1[] = new int[i];
            int sub2[] = new int[prices.length - i];
            for(int j = 0;j < i;j++)
                sub1[j] = prices[j];
            for(int j = i;j < prices.length;j++)
                sub2[j-i] = prices[j];
            int cur = subProfit(sub1)+subProfit(sub2);
            if(cur > max)
                max = cur;
        }
        return max;
    }
   
    private int subProfit(int[] prices) {
        if(prices.length == 0){return 0;}
        int opt = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length;i++){
            if(prices[i] < min)
                min = prices[i];
            opt = Math.max(prices[i] - min, opt);
        }
        return opt;


还有一种想法就是感觉最多两次交易应该是跟最大值最小值有关的，找出第一个递减区间之后的最大值和第二大值，以及最小值和第二小值，应该可以通过分类讨论得到答案，但是这样做感觉就是数学方法而不是计算机方法。

那么比较正确的思路应该是扩展成k然后去想一个通用的解法。




Improved Way: 被告知有DP的解法，于是决定自己先试着做一下，那么走正常DP的思路。

opt[i][j] //表示在0~j天里最多交易i次能获得的最大利润
// base case
opt[0][j] = 0 (0 <= j <= n)  最多交易0次无利润
opt[i][0] = 0 (0 <= i <= k) 在0天里无法交易
// itreation
opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))  可能与j-1天相同，可能增加一次交易。

这样的做法算法复杂度是O(kn^2)，空间复杂度是O(nk)

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                for(int t = 0;t < j;t++)
                    opt[i][j] = Math.max(opt[i][j], opt[i-1][t] + p[j-1] - p[t]);
            }
        }
        return opt[k][p.length];
    }


看了一下Discuss上的解法才知道这个世界牛人真多，在https://oj.leetcode.com/discuss/15153/a-clean-dp-solution-which-generalizes-to-k-transactions上这位提出了将第三层循环写入第二层循环的做法，让人大呼过瘾。

我们可以注意到以上逻辑关键的一步：opt[i][j] = max(opt[i][j-1], max(opt[i-1][t] + p[j]-p[t+1]))
分解下来就是
如果第i天无交易，那么就是opt[i][j] = opt[i][j-1].
如果做出交易决定，就要看在之前t天里正好做i-1次交易， 加上p[j]-p[t+1]这最后一次交易，哪一个第t天带来最大利润。
后半部分 max(opt[i-1][t] + p[j-1] - p[t])
           =    max(p[j-1] + (opt[i-1][t] - p[t]))
           =    p[j-1] + max(opt[i-1][t] - p[t])
           =    p[j-1] + preMax
其中max(opt[i-1][t] - p[t])这一部分，我们是可以用O(1)的时间写进第二层循环中的。
因为t的范围是[0,j)， 也就是说，每一次 for(int j = 1;j <= p.length;j++) 的循环末尾，我们都将当前opt[i-1][j] - p[j] 与之前一次的 preMax相比较，就可以得到新的preMax给下一次循环用了。而preMax的初始值就是opt[i-1][0] - p[0]了，因为正好 for(int j = 1;j <= p.length;j++) 这个循环中j是从1开始的。

这样算法复杂度就成了O(kn)，对应这一题就是O(n)了。

private int maxProfit(int[] p, int k){
        int opt[][] = new int[k+1][p.length+1];
        // base case
        for(int i = 0;i <= k;i++)
            opt[i][0] = 0;
        for(int j = 0;j <= p.length;j++)
            opt[0][j] = 0;
        // iteration
        for(int i = 1;i <= k;i++){
            int preMax = opt[i-1][0] - p[0];
            for(int j = 1;j <= p.length;j++){
                opt[i][j] = opt[i][j-1];
                opt[i][j] = Math.max(opt[i][j], preMax + p[j-1]);
                preMax = Math.max(preMax, opt[i-1][j]-p[j]);
            }
        }
        return opt[k][p.length];
    }

忽然有种感觉，以前算法课上很多DP的题目貌似都是要内层循环要遍历之前所有的，说不定都可以这样把之前所有的这个循环套入内层循环中。