[Function add]

Seanforfun · Seanforfun · commit a82587f2e0f5 · 2019-03-19T10:34:49.000-04:00
1. Add leetcode solutions with tag dp
diff --git a/leetcode/300. Longest Increasing Subsequence.md b/leetcode/300. Longest Increasing Subsequence.md
@@ -59,4 +59,87 @@ class Solution {
         return result;
     }
 }
-```
+```
+
+### Third time
+* Method 1: dp	O(N^2)
+	* dp[i]: the max increasing subarray up to current index.
+	```Java
+	class Solution {
+		public int lengthOfLIS(int[] nums) {
+			int len = nums.length;
+			if(len == 0) return 0;
+			int[] dp = new int[len];
+			Arrays.fill(dp, 1);
+			int max = 1;
+			for(int i = 1; i < len; i++){
+				for(int j = i; j >= 0; j--){
+					if(nums[i] > nums[j]){
+						dp[i] = Math.max(dp[i], dp[j] + 1);
+					}
+					max = Math.max(max, dp[i]);
+				}
+			}
+			return max;
+		}
+	}
+	```
+
+* Method 2: BST O(NlgN)
+	* we insert the values to tree in order and before inserting a node, we need to update the values.
+	```Java
+	class Solution {
+		private static class Node{
+			int val, count;
+			Node left, right;
+			public Node(int val, int count){
+				this.val = val;
+				this.count = count;
+			}
+		}
+		private Node root;
+		private int search(Node node, int val){
+			if(node == null) return 0;
+			int count = node.count;
+			int leftMax = 0, rightMax = 0;
+			if(val == node.val){
+				return search(node.left, val);
+			}else if(val < node.val){ // current node is at left side
+				return search(node.left, val);
+			}else{  // val > node.val
+				leftMax = search(node.left, val);
+				rightMax = search(node.right, val);
+				return Math.max(count, Math.max(leftMax, rightMax));
+			}
+		}
+		private void insert(Node node, int val, int count){
+			int cur = node.val;
+			if(cur == val){
+				node.count = count;   
+			}else if(cur < val){
+				if(node.right == null) node.right = new Node(val, count);
+				else insert(node.right, val, count);
+			}else{
+				if(node.left == null) node.left = new Node(val, count);
+				else insert(node.left, val, count);
+			}
+		}
+		public int lengthOfLIS(int[] nums) {
+			int len = nums.length;
+			if(len == 0) return 0;
+			else if(len == 1) return 1;
+			this.root = new Node(nums[0], 1);
+			int max = 1;
+			for(int i = 1; i < len; i++){
+				int count = search(root, nums[i]) + 1;
+				insert(root, nums[i], count);
+				max = Math.max(max, count);
+			}
+			return max;
+		}
+	}
+	```
+	
+	
+	
+	
diff --git a/leetcode/673. Number of Longest Increasing Subsequence.md b/leetcode/673. Number of Longest Increasing Subsequence.md
@@ -0,0 +1,61 @@
+## 673. Number of Longest Increasing Subsequence
+
+### Question
+Given an unsorted array of integers, find the number of longest increasing subsequence.
+
+```
+Example 1:
+
+Input: [1,3,5,4,7]
+Output: 2
+Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
+
+Example 2:
+
+Input: [2,2,2,2,2]
+Output: 5
+Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.
+```
+
+Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int. 
+
+### Solution
+* Method 1: dp
+    * dp[i]: up to current index, the max number of increasing subset.
+    * count[i]: the number of ways to keep the maximum dp number up to index i.
+        * update the maximum: we update the count to the previous ones, since we only need to append current value to all previous ones.
+        * if max is the same, we need to append current value to  all previous ways.
+    ```Java
+    class Solution {
+        public int findNumberOfLIS(int[] nums) {
+            int len = nums.length;
+            if(len == 0) return 0;
+            int[] dp = new int[len];
+            int[] count = new int[len];
+            Arrays.fill(dp, 1);
+            Arrays.fill(count, 1);
+            int max = 1;
+            for(int i = 1; i < len; i++){
+                for(int j = i - 1; j >= 0; j--){
+                    if(nums[i] > nums[j] && dp[j] + 1 > dp[i]){
+                        dp[i] = dp[j] + 1;
+                        count[i] = count[j];
+                    }else if(nums[i] > nums[j] && dp[j] + 1 == dp[i]){
+                        count[i] += count[j];
+                    }
+                }
+                max = Math.max(max, dp[i]);
+            }
+            int res = 0;
+            for(int i = 0; i < len; i++){
+                if(dp[i] == max){
+                    res += count[i];
+                }
+            }
+            return res;
+        }
+    }
+    ```
+
+### Reference
+1. [673. Number of Longest Increasing Subsequence 最长递增子序列的个数](https://blog.csdn.net/lanchunhui/article/details/51611970)
diff --git a/leetcode/72. Edit Distance.md b/leetcode/72. Edit Distance.md
@@ -94,3 +94,25 @@ class Solution {
     }
 }
 ```
+
+### Third time
+* Method 1: dp[i][j] This question is not difficult right now.
+	* dp[i][j]: The minimum actions up to index i in String A and index j in String B.
+	```Java
+	class Solution {
+		public int minDistance(String word1, String word2) {
+			int len1 = word1.length(), len2 = word2.length();
+			int[][] dp = new int[len1 + 1][len2 + 1];
+			for(int i = 0; i <= len1; i++)  dp[i][0] = i;
+			for(int i = 0; i <= len2; i++)  dp[0][i] = i;
+			char[] arr1 = word1.toCharArray(), arr2 = word2.toCharArray();
+			for(int i = 1; i <= len1; i++){
+				for(int j = 1; j <= len2; j++){
+					if(arr1[i - 1] == arr2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
+					else    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
+				}
+			}
+			return dp[len1][len2];
+		}
+	}
+	```
