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.

用一个二维数组进行DP，map[i][j] 表示T在长度前j位在S长度前i位合法的个数。当第i位和第j位char不同，我们只能考虑删掉第i位，相同时还能考虑保留第i为。

public class Solution {
    //Time: O(m * n)  Space: O(m * n)
    public int numDistinct(String S, String T) {
        if (S.length() < T.length()) {
            return 0;
        }
        
        int m = S.length();
        int n = T.length();
        int[][] map = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            map[i][0] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] += map[i - 1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    map[i][j] += map[i - 1][j - 1];
                }
            }
        }
        return map[m][n];
    }
}

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

用一个二维数组，map[i][j]  代表从word1(0,i)变化到word2(0,j)需要的次数。

public class Solution {
    //Time: O(m*n)  Space: O(m*n)
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        
        if (word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length() + 1;
        int n = word2.length() + 1;
        int[][] map = new int[m][n];
        for (int i = 1; i < m; i++) {
            map[i][0] = i;
        }
        for (int i = 1; i < n; i++) {
            map[0][i] = i;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    map[i][j] = map[i - 1][j - 1];
                } else {
                    int delete = map[i - 1][j] + 1;
                    int insert = map[i][j - 1] + 1;
                    int replace = map[i - 1][j - 1] + 1;
                    map[i][j] = Math.min(delete, Math.min(insert, replace));
                }
            }
        }
        return map[m - 1][n - 1];
    }
}

Triangle

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).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

类似一个滚动数组，做DP

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

Jump Game I && II

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

DP加贪心

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public boolean canJump(int[] A) {
        if (A == null || A.length <= 1) {
            return true;
        }
        
        boolean[] map = new boolean[A.length];
        map[0] = true;
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (map[j] && A[j] + j >= i) {
                    map[i] = true;
                    break;
                }
            }
        }
        return map[A.length - 1];
    }
}

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.)

DP加贪心，这道题不需要考虑跳不到终点的情况。

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public int jump(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        
        int[] map = new int[A.length];
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (j + A[j] >= i) {
                    map[i] = map[j] + 1;
                    break;
                }
            }
        }
        return map[A.length - 1]; 
    }
}

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.

DP: 用一个二维数组，map[i][j] = Math.min(map[i - 1][j] + grid[i][j], map[i][j - 1] + grid[i][j])，我们可以只用一维数组来代替。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int[] map = new int[grid[0].length];
        map[0] = grid[0][0];
        for (int i = 1; i < map.length; i++) {
            map[i] = map[i - 1] + grid[0][i];
        }
        for (int i = 1; i < grid.length; i++) {
            map[0] += grid[i][0];
            for (int j = 1; j < grid[0].length; j++) {
                map[j] = Math.min(map[j - 1] + grid[i][j], map[j] + grid[i][j]);
            }
        }
        return map[map.length - 1];
    }
}

Unique Paths I && II

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?

DP：用一个二维数组，map[i][j] 到此点可能的路线数量，map[i][j] = map[i - 1][j] + map[i][ j - 1]。我们可以用一个一维数组来代替。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        
        int[] map = new int[n];
        Arrays.fill(map, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                map[j] = map[j] + map[j - 1];
            }
        }
        return map[n - 1];
    }
}

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.

基本和上一题一样，只需判断是否为障碍物，如是设为0。

public class Solution {
    //Time: O(m*n)  Space: O(n)
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1) {
            return 0;
        }
        
        int[] map = new int[obstacleGrid[0].length];
        map[0] = 1;
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] == 1) {
                    map[j] = 0;
                } else if (j > 0) {
                    map[j] += map[j - 1];
                }
            }
        }
        return map[obstacleGrid[0].length - 1];
    }
}

Maximum Subarray

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.

DP，一个变量记录最大值，一个变量记录当前的和

public class Solution {
    //Time: O(n)  Space: O(1)
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(0, sum);
        }
        return max;
    }
}

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?

DP：map[i] = map[i - 1] + map[i - 2]

public class Solution {
    //Time: O(n)  Space: O(n)
    public int climbStairs(int n) {
        int[] map = new int[n + 1];
        map[0] = map[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            map[i] = map[i - 1] + map[i - 2];
        }
        return map[n];
    }
}

Unique Binary Search Trees I && II

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

比较巧妙的思路，假设我们有n个点，我们取i作为root，那左子树就是1到i - 1个点组成的情况，右子树就是i + 1到n组成的情况。把每个点作为root的情况进行累加，所以当我们知道1，2...n个点的组成树的种类，我们也能知道n + 1个点组成树的种类。

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public int numTrees(int n) {
        int[] map = new int[n + 1];
        map[0] = map[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                map[i] += map[j - 1] * map[i - j];
            }
        }
        return map[n];
    }
}

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
  return generate(1, n);
    }
    
    private ArrayList<TreeNode> generate(int start, int end) {
        ArrayList<TreeNode> bst = new ArrayList<TreeNode>();
        if (start > end) {
            bst.add(null);
            return bst;
        }
        
        for (int i = start; i <= end; i++) {
            ArrayList<TreeNode> left = generate(start, i - 1);
            ArrayList<TreeNode> right = generate(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode root = new TreeNode(i);
                    root.left = left.get(j);
                    root.right = right.get(k);
                    bst.add(root);
                }
            }
        }
        return bst;
    }
}

Best Time to Buy and Sell Stock I & II & III

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.

两个变量。一个记录当前最小值，一个记录当前最大利润。

public class Solution {
    //Time: O(n)  Space: O(1)
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int profit = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            profit = Math.max(profit, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return profit;
    }
}

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

比较直观的一道题，比较相邻的价格，如果后者大于前者，就把差值加进利润。

public class Solution {
    //Time: O(n)  Space: O(1)
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

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).

Best Time to Buy and Sell Stock的升级版。进行两次DP，第一次记录在时间点i前卖一次股票的收益，第二次记录在时间点i后卖一次股票的收益。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int max = prices[prices.length - 1];
        int min = prices[0];
        int[] pre = new int[prices.length];//存储在此点之前卖股票的收益
        int[] post = new int[prices.length];//存储在此点之后卖股票的收益
        
        for (int i = 1; i < prices.length; i++) {
            pre[i] = Math.max(pre[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        
        for (int i = prices.length - 2; i >= 0; i--) {
            post[i] = Math.max(post[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        
        max = 0;
        for (int i = 0; i < prices.length; i++) {
            max = Math.max(max, pre[i] + post[i]);
        }
        return max;
    }
}