Paint House leetcode

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

public class Solution {
    public int minCost(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int n = costs.length;
        int[][] dp = new int[n][3];
        for (int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }
        for (int j = 1; j < costs.length; j++) {
            dp[j][0] = costs[j][0] + Math.min(dp[j - 1][1], dp[j - 1][2]);
            dp[j][1] = costs[j][1] + Math.min(dp[j - 1][0], dp[j - 1][2]);
            dp[j][2] = costs[j][2] + Math.min(dp[j - 1][1], dp[j - 1][0]);
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));

    }
}

Maximal Square

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1; 
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max * max;
    }
}

House Robber II leetcode

Note: This is an extension of House Robber.

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.

第一次去掉第一家保留最后一家 第二次去掉最后一家保留第一家, 计算能抢得最大值, 然后拿结果比较取最大的.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        //include the first one
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        //include the last one
        int [] dr = new int[nums.length];
        dr[0] = 0;
        dr[1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            dr[i] = Math.max(dr[i - 1], dr[i - 2] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dr[nums.length - 1]);
    }
}

House Robber leetcode

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.

dp[i] 表示走第i步时候的最大抢劫量

递推公式 dp[i] = Math.max(dp[i - 1], dp[i -2] + nums[i - 1])

initial dp[0] = 0, dp[1] = nums[0]

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length + 1];
        
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}

Unique Paths II leetcode

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.

在第i个位置上设置一个障碍物后，说明位置i到最后一个格子这些路都没法走 为0

所以说明，在初始条件时，如果一旦遇到障碍物，障碍物后面所有格子的走法都是0

再看求解过程，当然按照上一题的分析dp[i][j] = dp[i-1][j] + dp[i][j-1] 的递推式依然成立.碰到了障碍物，那么这时的到这里的走法应该设为0，因为机器人只能向下走或者向右走，所以到这个点就无法通过。

时间O(m*n) 空间O(m*n) 

public class Solution {
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][] sum = new int [m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] != 1) {
                sum[i][0] = 1;
            } else {
                break;//后面所有的都无法到达所以break
            }
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] != 1) {
                sum[0][j] = 1;
            } else {
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    sum[i][j] = sum[i-1][j] + sum[i][j-1];
                } else {
                    sum[i][j] = 0;
                }
            }
        }
        return sum[m-1][n-1];
        
    }
}

动态规划总结

When to use DP?

• Input cannot sort
• Find minimum/maximum result
• Check the feasibility 找可行性
• Count all possible solutions 列出所有解

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

4 Types of DP

• 1. Matrix DP (10%)
• 2. Sequence (40%)
• 3. Two Sequences DP (40%)*
• 4. Backpack (10%)

通用解法：

1.  状 态 State

2. 方程 Function
状态之间的联系，怎么通过小的状态，来算大的状态

3. 初始化 Intialization
最极限的小状态是什么, 起点

4. 答案 Answer
最大的那个状态是什么，终点

Matrix DP

• state: f[x][y] 表示我从起点走到 坐 标x,y……
• function: 研究走到xy 这个点之前的一步是从哪里走的
• intialize: 起点
• answer: 终点

Sequence Dp

• state: f[i]表示“ 前i”个位置/数字/字母,(以第i个为)...
• function: f[i] = f[j] … j 是i之前的一个位置
• intialize: f[0]..
• answer: f[n-1]..

Two Sequences Dp

• state: f[i][j]代表了第一个sequence的前i个数字/字符 配上第二个sequence的前j个...
• function: f[i][j] = 研究第i个和第j个的匹配关系
• intialize: f[i][0] 和 f[0][i](二维数组都要初始化第0行和第0列)
• answer: f[s1.length()][s2.length()]

1. sequences
Climbing Stairs

Decode Ways

Unique Binary Search Trees

Maximum Subarray

Maximum Product Subarray

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock III

Word Break

Palindrome Partitioning II

2. Matrix

Triangle

Unique Paths I

Unique Paths II

Minimum Path Sum

3. two sequences

Edit Distance

Distinct Subsequences

Interleaving String

Scramble String(3 sequences)

Maximal Rectangle leetcode

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
解法转自:http://codeganker.blogspot.com/2014/04/maximal-rectangle-leetcode.html

"这道题的解法灵感来自于Largest Rectangle in Histogram这道题，假设我们把矩阵沿着某一行切下来，然后把切的行作为底面，将自底面往上的矩阵看成一个直方图（histogram）。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。
算法的基本思路已经出来了，剩下的就是一些节省时间空间的问题了。
我们如何计算某一行为底面时直方图的高度呢？ 如果重新计算，那么每次需要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹，如果我们知道上一行直方图的高度，我们只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。利用历史信息，我们就可以在线行时间内完成对高度的更新。我们知道，Largest Rectangle in Histogram的算法复杂度是O(n)。所以完成对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次，那么算法总时间复杂度是O(m*n)。
空间上，我们只需要保存上一行直方图的高度O(n)，加上Largest Rectangle in Histogram中所使用的空间O(n)，所以总空间复杂度还是O(n)。代码"

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0 || matrix == null) {
            return 0;
        }
        int m = matrix.length;//列数
        int n = matrix[0].length;//行数
        int[] height = new int[n];//对每一列构造数组
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    height[j] = 0;
                } else {
                    height[j] += 1;
                }
            }
            max = Math.max(helper(height), max);//从上至下每层
        }
        return max;
    }
    public int helper(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= height.length; i++) {
            int h;
            if (i == height.length) {// fake一个最终高度为1的直放
                h = 0;
            } else {
                h = height[i];//当前高度
            }
            while (!stack.isEmpty()) {
                if (h < height[stack.peek()]) {
                    int indx = stack.pop();
                    int k = i;//计算直方的底用于求面积
                    if (!stack.isEmpty()) {
                        k = i - stack.peek() - 1;
                    }
                    max = Math.max(max, k*height[indx]);
                } else {
                    break;
                }
            }
            stack.push(i);
        }
        return max;
    }
}

Jump Game II leetcode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

state:f[i] 表示从0到i点最少要跳几部

function： f[i] = f[j] +1 // j< i   j + a[j] >= i 取最小的j

initial：f[0] = 0

return f[a.length-1]
时间O(n^2) 空间O(n)

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    break;
                }
            }
        }
        return count[A.length - 1];
    }
}

如果要输出所有解（从0点jump到i点的路径）

public class Solution {
    public int jump(int[] A) {
        int[] count = new int[A.length];
        int[] pre = new int[A.length];
        count[0] = 0;
        for (int i = 1; i < A.length; i++) {
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (count[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    count[i] = count[j] + 1;
                    pre[i] = j;//记录到达i点的前一点j
                    break;
                }
            }
        }
        i = A.length - 1;
        while(i != 0) {
            path.add(i);//把i的值加入结果里
            i = pre[i];//i的值编程i前一点的值
        }
        path.add(0);
        path.reverse;//因为是倒着加的所以要reverse
        return path;
    }
}

greedy解法 在位置i可以跳的最远距离为nums[i] + i , 每次跳完更新max = max(max, num[i] + i)
时间O(n) 空间 O(1)

public class Solution {
    public int jump(int[] nums) {
        int max = 0;
        int lastmax = 0;
        int step = 0;
        for (int i = 0; i <= max && i < nums.length; i++) {
            if (i > lastmax) {//在第0位置 如果i大于0的话就至少走一步, 更新lastmax为0位置走一步最远能到的位置
                lastmax = max;
                step++;
            }
            max = Math.max(max, nums[i] + i);
        }
        if (max < nums.length - 1) {
            return 0;
        }
        return step;
    }
}

Best Time to Buy and Sell Stock III leetcode

Say you have an array for which the ith 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).

可以做两次交易, 所以划分两个区间left 长度为0 ~ i, right 长度为 i ~ len-1

left[i] 表示在i点之前买进并卖出能获得的最大利润 

维护一个最小值min, 每次递归的profit最大值为max[A[i] - min, profit]

right[i]表示i点之后买进 最终之前卖出的最大利润

维护一个最大值max 每次递归profit最大值为max[profit, max - A[i]]

所以利润为profit[i] = left[i] + right[i]

最终的最大利润就是Max(profit[i])
时间O(n)空间O(n)

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0 || prices == null) {
            return 0;
        }
        int len = prices.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < len; i++) {
            min = Math.min(min, prices[i]);
            left[i] = Math.max(left[i-1], prices[i] - min);
        }
        right[len - 1] = 0;
        int max = prices[len - 1];
        for (int j = len - 2; j >= 0; j--) {
            max = Math.max(max,prices[j] );
            right[j] = Math.max(right[j + 1],max -prices[j]);
        }
        int profit = 0;
        for (int k = 0; k < len; k++) {
            profit = Math.max(profit, left[k] + right[k]);
        }
        return profit;
    }
}

Triangle leetcode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

自底向上求解,

state:dp[i][j] 表示自底向上到第i行第j个数的最小路径

initial: dp[n][i] = triangle最后一个数组的值

function:dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j) 最小值由当前点的值加上下一行相邻两个路径值最小的路径

return: dp[0][0]
time : O(n^2)

//O(n^2)space

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int n = triangle.size();
        int[][] dp = new int[n ][n ];
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = z; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}
//O(n) space

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int n = triangle.size();
        int[]dp = new int[n];
        for (int i = 0; i < n; i++) {
           dp[i] = triangle.get(n - 1).get(i); 
        }
        for (int i = n-2; i>= 0; i--) {
            for (int j =0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

Scramble String leetcode

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

state:dp[i][j][len] 

这道题我们维护一个三维动态规划量dp[i][j][len] 其中i为s1的起始位置, j为s2的起始位置, len为长度

dp[i][j][len]表示s1从i位到i+ len位置 与 s2从j位到j+len位是否是Scramble String 

初始化:dp[i][j][1] = s1.charAt(i) == s2.charAt(j) 如果s1的i位与s2的j位字母相同 则为true

function: dp[i][j][len] = dp[i][j][l] && dp[i + l][j + l][len - l] || dp[i][j + len - l][l] && dp[i + l] [j][len - l] 

有两种情况为true:

1. 存在着一点k (0 < k < len)使得s1.substring(i, i+k) 和 s2.substring(j, j+k) 为Scramble String  s1.substing(i + k, i +len), s2.substring(j +k, j + len)为Scramble String 就是说s1左边的substring和s2左边的substirng s1右边的substring 和s2右边的substring  为Scramble String  

2. 存在着一点k (0 < k < len)使得s1.substring(i, i+k) 和 s2.substring(j +len - k, j + len)  为Scramble String  s1.substing(i+k, i +len), s2.substring(j, j + len - k)为Scramble String 就是说s1左边的substring和s2右边的substirng s1右边的substring 和s2左边的substring  为Scramble String 

return: dp[0][0][n]

时间O(n^4) 空间 O(n^3)

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int n = s1.length();
        boolean[][][] dp = new boolean[n][n][n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][1] = s1.charAt(i) == s2.charAt(j);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                for (int len = 1; len <= n - Math.max(i, j); len++) {
                    for (int l = 1; l < len; l++) {
                        if (dp[i][j][l] && dp[i + l][j + l][len - l] || dp[i][j + len - l][l] && dp[i + l] [j][len - l]) {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                    // }
                }
            }
        }
        return dp[0][0][n];
    }
}

Best Time to Buy and Sell Stock leetcode

Say you have an array for which the ith 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.

维护一个最小值min, 每次递归的profit最大值为max[A[i] - min, profit]
时间复杂O(n) 空间复杂O(1)

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

Maximum Product Subarray leetcode

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

与maximum subarray不同, 这道题不仅要维护一个max 还要维护一个min
时间复杂度为O(n). 

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] max = new int[len];
        int[] min = new int[len];
        max[0] = min[0] = nums[0];
        int res = max[0];
        for (int i = 1; i < len; i++) {
        
            max[i] = Math.max(Math.max(nums[i], max[i-1] * nums[i]), min[i-1] * nums[i]);
            min[i] = Math.min(Math.min(nums[i], min[i-1] * nums[i]), max[i-1] * nums[i]);
            res = Math.max(res, max[i]);
 
        }
        return res;
    }
}
public class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int a = nums[i] * max;//a,b需要提前算出 因为算min时候max值会变化
            int b = nums[i] * min;
            max = Math.max(nums[i], Math.max(a, b));
            min = Math.min(nums[i], Math.min(a, b));
            res = Math.max(max, res);
        }
        return res;
    }
}

Maximum Subarray leetcode

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

对于sum[i] 最大的情况有两种 一种是和前边其他的数一起组成最大 一中是单独自己组成最大 所以每次sum[i] 要判定哪个大就取哪个作为sum[i] 的值

state:sum[i]表示 largest sum

initial sum[0] = nums[0]

function: sum[i] = Math.max(sum[i-1] + nums[i], nums[i])     max = math.max(max, sum[i])

return max
时间复杂度为O(n)

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] sum = new int[len];
        int max = nums[0];
        sum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            sum[i] = Math.max(sum[i - 1] + nums[i], nums[i]);
            max = Math.max(max, sum[i]);
        }
        return max;
    }
}

Unique Binary Search Trees leetcode

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

分析转自:http://www.cnblogs.com/springfor/p/3884009.html

   这题想了好久才想清楚。其实如果把上例的顺序改一下，就可以看出规律了。 

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

   比如，以1为根的树有几个，完全取决于有二个元素的子树有几种。同理，2为根的子树取决于一个元素的子树有几个。以3为根的情况，则与1相同。

    定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目，

    如果数组为空，毫无疑问，只有一种BST，即空树，
    Count[0] =1

    如果数组仅有一个元素{1}，只有一种BST，单个节点
    Count[1] = 1

    如果数组有两个元素{1,2}， 那么有如下两种可能
    1                       2
     \                    /
       2                1
    Count[2] = Count[0] * Count[1]   (1为根的情况)
                  + Count[1] * Count[0]  (2为根的情况。

    再看一遍三个元素的数组，可以发现BST的取值方式如下：
    Count[3] = Count[0]*Count[2]  (1为根的情况)
                  + Count[1]*Count[1]  (2为根的情况)
                  + Count[2]*Count[0]  (3为根的情况)

    所以，由此观察，可以得出Count的递推公式为
    Count[i] = ∑ Count[0...k] * [ k+1....i]     0<=k<i-1
    问题至此划归为一维动态规划。

   [Note]
    这是很有意思的一个题。刚拿到这题的时候，完全不知道从那下手，因为对于BST是否Unique，很难判断。最后引入了一个条件以后，立即就清晰了，即
    当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：
   以i为根节点的树，其左子树由[1, i-1]构成， 其右子树由[i+1, n]构成。 

” 

同时为了根据递推式来写程序，需要将递推式简化一下。

根据卡特兰数，C0Cn+1，因为leetcode输入的参数是n，所以为了避免混淆，这里递推式写成Ct+1,初始值为C0 = 1。

原始的递推式是： Ct+1 += Ci*Ct-i (0<= i <=t)

现在令变量num=t+1，那么t=num-1

所以原始递推式做变量替换得：Cnum += Ci*Cnum-1-i (0<= i <=num-1) 

而num的取值范围是[1, n]因为C0已知。

state : res[n]表示total number of BST
initial : res[0] = 1 res[1] = 1
function: res[n] = res[j] *res[n-j-1] 0 < j <n
answer: res[n]

每个i需要循环两次得到答案， 时间为O(n^2) 空间O(n) 

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

Minimum Adjustment Cost

Given an integer array, adjust each integers so that the difference of every adjcent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]| 

Example

Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it's minimal. Return 2.

Note

You can assume each number in the array is a positive integer and not greater than 100

注意是positive number 所以j的起始值是1不是0 因为这个犯了好几次错....

state: dp[i][v] 表示前i个数, 第i个数调整为v 满足条件, 所需要的最小代价

function:如果i个数时j 那么第i-1个数k是要满足 Math.abs(j - k) < target的

dp[i][v] = Math.min(dp[i-1][k] +  Math.abs(j -A.get(i-1))) //第i个数时j 第i-1个数为k时候使代价最小

如果第i个数是j, 那么第i-1个数k只能在[lowerRange, UpperRange]之间，lowerRange=Math.max(0, j-target), upperRange=Math.min(99, j+target), 这样的话，transfer function可以写成： for (int p=lowerRange; p<= upperRange; p++) { 　　res[i][j] = Math.min(res[i][j], res[i-1][k] + Math.abs(j-A.get(i-1))); }

initial:dp[0][j]= 0

return: 满足条件的最小代价 Math.min(dp[m][j]) // 改变j的值找到最小的代价

public class Solution {

    public int MinAdjustmentCost(ArrayList A, int target) {
        int m = A.size();
        int[][] dp = new int[m+1][101];
        for (int j = 0; j < 101; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= 100; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 1; k <= 100; k++) {
                    if (Math.abs(j - k) > target) {
                        continue;
                    }
                 
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][k] +  Math.abs(j -A.get(i-1)));

//Math.abs(j -A.get(i-1)))表示第i个数改为j所需代价

                }
            }
        }
        int result = Integer.MAX_VALUE;
        for (int j = 1 ; j <= 100; j++) {
            result = Math.min(result, dp[m][j]);
        }
        return result;
    }
}

k Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example

Given [1,2,3,4], k=2, target=5. There are 2 solutions:

[1,4] and [2,3], return 2.

state:dp[i][j][t] 前i个数取出j个和为t 所以j必须要小于i

function: dp[i][j][t] = dp[i-1][j][t] 如果t >= A中第i个数 dp[i][j][t] += dp[i-1][j-1][t-A[i-1]]

（1）我们可以把当前A[i - 1]这个值包括进来，所以需要加上D[i - 1][j - 1][t - A[i - 1]]（前提是t - A[i - 1]要大于0）

（2）我们可以不选择A[i - 1]这个值，这种情况就是D[i - 1][j][t]，也就是说直接在前i-1个值里选择一些值加到target.

initial: dp[i][0][0] = 0

return: dp[i][k][target]

public class Solution {

    public int kSum(int A[], int k, int target) {
        int m = A.length;
        int[][][] dp = new int[A.length + 1][k+1][target+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= k && j <= i; j++) {// j必须要比i小
                for (int n = 1; n <= target; n++) {
                    dp[i][j][n] = dp[i-1][j][n];
                    if (n >= A[i-1]) {// 是大于等于不是大于
                        dp[i][j][n] += dp[i-1][j-1][n- A[i-1]];
                    }
                    
                }
            }
        }
        return dp[m][k][target];
        
    }
}

Backpack I & II

Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? 

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

n个整数a[1..n]，装m的背包

• state: f[i][j] “前i”个数，取出一些能否组成和为j
• function: f[i][j] = 如果不取最后第i个数f[i-1][j]  or 如果考虑第i个数 那么首先A[i] < j 成立的话 f[i-1][j - a[i]]

• intialize: f[X][0] = true; f[0][1..m] = false
• answer: 能够使得f[n][X]最大的X(0<=X<=m)

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        boolean [][] dp = new boolean[A.length + 1][m+1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = false;
        }
        for (int i = 0; i <= A.length; i++) {
            dp[i][0] = true;
        }
        for (int i =1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];//不取第i个数
                if (j >= A[i-1] && dp[i-1][j - A[i-1]]) {//取第i个数 A[i-1]表示第i个数
                    dp[i][j] = true;
                }
            }
        }
        for (int k = m; k >=0; k--) {
            if (dp[A.length][k]) {
                return k;
            }
        }
        return 0;
    }
}

Given n items with size A[i] and value V[i], and a backpack with size m. What's the maximum value can you put into the backpack?

Example

Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.

• state: f[i][j] “前i”个数，放入大小为j的背包获得的最大value
• function: f[i][j] = max{f[i-1][j],f[i-1][j-c[i]]+v[i]}         
• “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f[i-1][j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-c[i]的背包中”，此时能获得的最大价值就是f[i-1][j-c[i]]再加上通过放入第i件物品获得的价值V[i]。

• intialize: f[X][0] = 0; f[0][1..m] = 0
• answer: f[A.length][m]

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        int[][] dp = new int[A.length + 1][m + 1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }
        for (int i = 0; i <= A.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }
}

Interleaving String leetcode

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

思路: 来自http://blog.csdn.net/u011095253/article/details/9248073

dp[i][j]表示s1取前i位，s2取前j位，是否能组成s3的前i+j位

举个列子，注意左上角那一对箭头指向的格子dp[1][1], 表示s1取第1位a, s2取第1位d，是否能组成s3的前两位aa

从dp[0][1] 往下的箭头表示，s1目前取了0位，s2目前取了1位，我们添加s1的第1位，看看它是不是等于s3的第2位，( i + j 位）

从dp[1][0] 往右的箭头表示，s1目前取了1位，s2目前取了0位，我们添加s2的第1位，看看它是不是等于s3的第2位，( i + j 位)

那什么时候取True，什么时候取False呢？

False很直观，如果不等就是False了嘛。

那True呢？首先第一个条件，新添加的字符，要等于s3里面对应的位( i + j 位)，第二个条件，之前那个格子也要等于True

举个简单的例子s1 = ab, s2 = c, s3 = bbc ，假设s1已经取了2位，c还没取，此时是False（ab!=bb），我们取s2的新的一位c，即便和s3中的c相等，但是之前是False，所以这一位也是False

同理，如果s1 = ab, s2 = c, s3=abc ，同样的假设，s1取了2位，c还没取，此时是True（ab==ab），我们取s2的新的一位c,和s3中的c相等，且之前这一位就是True，此时我们可以放心置True （abc==abc)

state: dp[i][j] s1取前i个字符 s2取前j个字符 s3取前i+1字符 是否能匹配
function:  如果最后一位(i+j位)与s1的最后一位(i位)相等 dp[i][j] = dp[i-1][j]
与s2最后一位相等则dp[i][j] = dp[i][j-1]
initial: dp[0][0] = true dp[i][0] dp[0][j]看s1 s2 s3比较
返回: dp[s1.length][s2.length]
时间和空间都是O(m * n)

声明数组dp[s1.length+1][s2.length+1] string 的index 和dp的index 相差1

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if (l1 + l2 != l3) {
            return false;
        }
        boolean [][] dp = new boolean[l1+1][l2+1];
        dp[0][0] = true;
        for (int i = 1; i <= l1; i++) {
            if (s3.charAt(i-1) == s1.charAt(i-1) && dp[i-1][0]) {
                dp[i][0] = true;
            }
        }
        for (int j = 1; j <= l2; j++) {
            if (s3.charAt(j-1) == s2.charAt(j-1) && dp[0][j-1]) {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i<= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j]) {
                    dp[i][j] = true;
                }
                if (s3.charAt(i+j-1) == s2.charAt(j-1) && dp[i][j-1]) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[l1][l2];
    }
}

Distinct Subsequences leetcode

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.

简单翻译一下，给定两个字符串S和T，求S有多少个不同的子串与T相同。S的子串定义为在S中任意去掉0个或者多个字符形成的串。

  0 r a b b b i t

0 1 1 1 1 1 1 1 1

r 0 1 1 1 1 1 1 1

a 0 0 1 1 1 1 1 1

b 0 0 0 1 2 3 3 3

b 0 0 0 0 1 3 3 3

i 0 0 0 0 0 0 3 3

t 0 0 0 0 0 0 0 3  

state: dp[i][j] 表示S串中从开始位置到第i位置与T串从开始位置到底j位置匹配的子序列的个数

function: dp[i][j] = dp[i][j-1] 就是说假设S已经匹配了j-1个字符,无论S[j]和T[i]是否匹配, 至少是dp[i][j-1]

如果匹配, 我们可以让S[j]和T[i]匹配，然后让S[j - 1]和T[i - 1]去匹配 (由图得关系)

dp[i][j] += dp[i-1][j-1]

initial: f[i][0] = 0 f[0][j] = 1 空集也是subsequences

return dp[m][n]
时间和空间都是O(m * n)

public class Solution {
    public int numDistinct(String s, String t) {
        int m  = s.length();
        int n = t.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i<= n; i++) {
            dp[i][0] = 0;
        } 
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i][j-1];
                if (t.charAt(i-1) == s.charAt(j-1)) {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[n][m];
        
    }
}