152. Maximum Product Subarray

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.

思路: 乘积的最大值可能来自于两个正数相乘或者两个负数相乘。所以我们要同时来保存每次乘积的最大值跟最小值.
复杂度: time O(n), space: O(n)

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] maxProds = new int[nums.length];
        int[] minProds = new int[nums.length];
        int res = nums[0];
        maxProds[0] = minProds[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxProds[i] = Math.max(nums[i], maxProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], minProds[i-1] * nums[i]);
            } else {
                maxProds[i] = Math.max(nums[i], minProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], maxProds[i-1] * nums[i]);
            }
            res = Math.max(maxProds[i], res);
        }
        return res;
    }
}

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

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路: DP的思路,用一个curSum跟maxSum来追踪.
复杂度 time O(n) space O(1)

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 
            return Integer.MIN_VALUE;
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i &lt; nums.length; i++) {
            curSum = curSum &gt; 0 ? curSum + nums[i]: nums[i];
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }
}

198. House Robber I/II

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.

思路:
复杂度: Time O(n), Space O(n)

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] money = new int[nums.length + 1];
        money[0] = 0; // 第0次抢了0
        money[1] = nums[0]; // 第一次抢的nums[0]
        for (int i = 2; i &lt; nums.length + 1; i++) {
            money[i] = Math.max(money[i - 1], money[i - 2] + nums[i - 1]);
        }
        return money[nums.length];
    }
}

房子成环。
思路: 抢第一个就不能抢最后一个,不抢第一个抢不抢最后一个随意
两种情况:
1.抢第一间(第二间必须不抢,第三间随意),不抢最后一间(倒数第二间随意)
2.不抢第一间(第二间随意),最后一间抢不抢随意(倒数第二间也随意)

public class Solution {
    // 1 2 4 6 4
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int n = nums.length;
        int[] robFirst = new int[n+1];
        int[] notRobFirst = new int[n+1];
        // init 
        robFirst[1] = nums[0];
        robFirst[2] = robFirst[1];
        notRobFirst[1] = 0;
        notRobFirst[2] = nums[1];

        for (int i = 3; i &lt;= n - 1; i++) { // 第三次抢到n-1次
            robFirst[i] = Math.max(nums[i - 1] + robFirst[i - 2], robFirst[i - 1]);
        }
        for (int i = 3; i &lt;= n; i++) { // 第三次抢到第n次
            notRobFirst[i] = Math.max(nums[i - 1] + notRobFirst[i - 2], notRobFirst[i-1]);
        }

        return Math.max(robFirst[n - 1], notRobFirst[n]);

    }
}

Matrix 跟Sequence的DP总结

Matrix的DP,二维数组

64 Minimum Path Sum: 对于每个点,只能往下走或者往右边走,所以每个点path sum的值来源于上面点或者左边点。
State: f[x][y]从起点走到x,y的最短路径
Function: f[x][y] = min(f[x-1][y], f[x][y-1]) + matrix[x][y]
initialize: f[0][0] = matrix[0][0], 对于二维数组要想f[i][0]跟f[0][i]如何初始化:
//f[i][0] = sum(0, 0 -> i, 0) 初始化最左边
//f[0][i] = sum(0, 0-> 0, i) 初始化最上边
Answer: f[n-1][m-1]

63 Unique Paths II,某些点不能走(obstacle),
不能走的点之间算为0就可以,用个if语句去check.

Sequence的DP,一维数组

State: f[i]表示”前i”个位置/数字/字母,
function: f[i]= f[j]….j是i之前的一个位置
initialize: f[0]..
answer: f[n-1]..

70 Climbing Stairs(爬楼梯)
state: f[i]表示前i个位置, 调到第i个位置的方案总数
function: f[i]=f[i-1]+f[i-2]
initialize:f[0]=1
answer: f[n]

  1. Jump Game
    state: f[i]表示能否从起点调到第i个位置
    function: f[i] = OR(f[j], j A[j] + j >= i && f[j]=true
    initialize: f[0]=true
    answer:f[n-1]

  2. Palindrome Partitioning II
    求最少的分割次数,
    state: f[i]为”前”i个字符组成的子字符串需要最少几次cut()
    function: f[i] = Min{f[j] + 1, j<i && j+1 ~ i 这段是一个palindrome}
    initialize: f[i]=i – 1(f[0]=0)
    answer:f[s.length()]

  3. Word Break
    state: f[i]为"前i"个字符能否被完美切分
    function: f[i]=OR{f[j], j<i, j+1 ~ i是一个词典中的单词}
    initialize: f[0]=true
    answer: f[s.length()]
    O(NL), N:字符串长度. L:最长单词的长度

120. 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的经典题目,用Divide&Conquer的思路来实现,每走一步都有两个选择: 往下走跟往右走. 总体来说走下来时间复杂度有点高为O(2^n). 简单写一下用DFS实现分治的解法

public int miniPath(int[][] triangle) {
    return dfs(triangle, 0, 0);
}

public int dfs(int[][], triangle, int x, int y) {
    if (x == triangle.length - 1) {
        return 0;
    }
    int left = dfs(triangle, x + 1, y);
    int right = dfs(triangle, x + 1, y + 1);
    return Math.min(left, right) + triangle[x][y];
}

同时给下traverse的思路:

//traverse
public void dfs(int[][] triangle, int x, int y, int sum) {
    if (x == triangle.length) {
        if (sum <  miniSum) {
            miniSum = sum;
        }
        return;
    }
    dfs(triangle, x + 1, y, sum + triangle[x][y]);
    dfs(triangle, x + 1, y + 1, sum + triangle[x][y]);
}

DFS过程中, 很多点被重复计算,导致时间复杂度特别高,我们可以加cache来降低时间复杂度.
把时间复杂度降到O(n^2).

class Point {
   int x;
   int y; 
   public Point(int x, int y) {
       this.x = x;
       this.y = y;
   }
}
public int dfs(int[][], triangle, Point point, HashMap<Point, Integer> map) {
    if (point.x == triangle.length - 1) {
        return 0;
    }
    if (map.containsKey(point)) {
        return map.get(point);
    }
    int left = dfs(triangle, point.x + 1, point.y);
    int right = dfs(triangle, point.x + 1, point.y + 1);
    Point newValue =  Math.min(left, right) + triangle[point.x][point.y];
    map.put(point, newValue);
    return map.get(point);
}

我们还可以用循环DP的方式来解决这个问题:
1. Down -> Top approach
2. Top-> Down approach
对于这个题目,如果我们从底部往上开始走,每层取最小值,

1. Down -> Top approach

// 状态定义
f[i][j] 用来表示i,j出发走到最后一层的最小路径长度
n = triangle.length;
// 初始化数组
for (int i = 0; i < n; i++) {
    f[n-1][i] = triangle[n-1][i];
}
// 循环递归求解
for (int i = n - 2; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        f[i][j] = Math.min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
    }
}
// 求结果: 起点
f[0][0]

2. Top-> Down approach

对于本题,自顶向下的方法略复杂些,主要是因为要check一些边界条件:

// 状态定义
f[i][j] 用来表示0,0出发,走到i,j的最小路径长度
n = triangle.length;
// 初始化
f[0][0] = triangle[0][0]

// 循环递归求解
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= i; j++) {
        f[i][j] = OO
        if(i - 1, j 存在) {
            f[i][j] = Math.min(f[i][j], f[i-1][j]) + triangle[i][j];
        }
        if(i - 1, j - 1存在) {
            f[i][j] = Math.min(f[i - 1][j - 1], f[i][j]) + triangle[i][j]
        }
    }
}

// 求结果:
Math.min(f[n-1][0],f[n-1][1],f[n-1][2]…..);

DP的总结:

什么时候用DP来解呢? 一般有以下几个情况可以考虑用DP来做:
1. 求minimum或者maximum的问题
2. 求Yes/No的问题
3. 求个数(Count)的问题
4. 当给的条件不能sort或者swap的时候,可以考虑用DP

DP的四个要素

  1. 状态 State
  2. 转换方程Function
  3. 初始化(起点)
  4. 终点(答案)

大概面试中常见的DP类型

  1. MatrixDP(10%), 二维数组
  2. Sequence(40%), 一维数组
  3. Two Sequences DP(40%)
  4. Backpack(10%)

139. 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”.

思路:如果给定单词可以被分解,那么在字典中都可以找到对应的每一块, 我们需要找到这样的分割点。这里有一个条件那就是这个单词的最后一个分割点到单词末尾组成的substring肯定会出现在字典中,从这个分割点开始往前也是可以分解在字典中找到对应的单词。 我们可以用DP的思想来做这个题目, 从后往前来验证。 外层循环可以从后往前来挨个遍历单词每个字符,内层循环来找这样的分割点到单词末尾之间组成的所有substring是否有存在在字典当中。我们用一个boolean 数组来表示,某个点i到单词末尾组成的所有的可能的substring的集合是否有在Dict中出现过。依次从后往前找,直到最后返回数组第一个值即可。

复杂度: Time: O(n^2), Space: O(n)

public class Solution {
    public boolean wordBreak(String s, Set&lt;String&gt; wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[s.length()] = true;
        for (int i = s.length() - 1; i &gt;= 0; i--) {
            for(int j = i; j &lt; s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (wordDict.contains(sub) &amp;&amp; dp[j + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}

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

思路: 我们可以用一个array来记录走过的点的和, 这里我们的array起名叫curSum, 表示的是从某个点开始,累计走过的点的和。指针在走的过程中,我们要保证curSum中的和比较大。所以我们要比较前一个点的curSum是否大于0, 如果大于0,我们把前一个点的curSum加上当前点的值, 否则我们把当前点的值作为curSum。 因为要找出最大的subarray的和,我们需要维持一个global 的maxSum值。

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 
            return Integer.MIN_VALUE;
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curSum = curSum > 0 ? curSum + nums[i]: nums[i];
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }
}