Dynamic Programming(动态规划）
Outline：
- 从递归到动态规划
- 什么情况用动态规划
- 动态规划在面试中的常见类型
从递归到动态规划
动态规划(Dynamic Programming)常常适用于解决有重复子问题(overlap subproblem)和最优子结构性质(optimal substructure)的问题。而我们在解决一些问题(比如Tree类)时，常常会用到分治(Divide & Conquer)的思想，也就是将这一个问题分成几个子问题(subproblem)解决。而当这些子问题中有多重复子问题时，我们就用到了动态规划。所以说动态规划思想的核心就是试图仅仅解决每个子问题一次，而将已经解决的子问题通过某种方式记忆化存储。这样大大减少了计算量，从而提高了问题的解决效率。
我们通过一道典型的动态规划入门题目，来更近一步说明递归和动态规划的关系
Leetcode. 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).
这道题传统的递归解法：
- Divide & Conquer
- DFS
Divide & Conquer 和 DFS两种方法的区别在于前者直接将结果作为返回值而后者这一般将结果作为传入参数，有时也会用到全局变量。这一点会在Tree的遍历中有跟明显的区别。(具体详见树)
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.isEmpty()) return 0;
return minimumTotalHelper(0,0,triangle);
}
private int minimumTotalHelper(int x, int y, List<List<Integer>> triangle){
if(x >= triangle.size() || y >= triangle.get(x).size()) return 0;
return triangle.get(x).get(y) + Math.min(minimumTotalHelper(x+1,y,triangle),minimumTotalHelper(x+1,y+1,triangle));
}
}
public class Solution {
int min = Integer.MAX_VALUE;
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.isEmpty()) return 0;
minimumTotalHelper(0,0,triangle,0,0);
return min;
}
private void minimumTotalHelper(int x, int y, List<List<Integer>> triangle, int height, int sum){
if(height == triangle.size()){
min = Math.min(sum, min);
}
if(x <triangle.size() && y <triangle.get(x).size()){
minimumTotalHelper(x+1,y,triangle,height+1, sum+triangle.get(x).get(y));
minimumTotalHelper(x+1,y+1,triangle,height+1,sum+triangle.get(x).get(y));
}
}
}
假设三角形的高度是n，这两种递归方法的复杂度O(n^2)。因为在计算的过程中，重复计算了许多子问题，所以时间复杂度较高。所以我们就需要用到动态规划。
- (记忆化搜索)Divide & Conquer + Memoriazation
多重循环
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if(triangle.isEmpty()) return 0; int[][] map = new int[triangle.size()][triangle.size()]; return minimumTotalHelper(0,0,triangle,map); } private int minimumTotalHelper(int x, int y, List<List<Integer>> triangle,int[][] map){ if(x >= triangle.size() || y >= triangle.get(x).size()) return 0; if(map[x][y] != 0) return map[x][y]; map[x][y]= triangle.get(x).get(y) + Math.min(minimumTotalHelper(x+1,y,triangle,map),minimumTotalHelper(x+1,y+1,triangle,map)); return map[x][y]; } }public class Solution { public int minimumTotal(List<List<Integer>> triangle) ｛ int[][] dp = new int[triangle.size()][triangle.size()]; for(int i = 0; i < triangle.size(); i++){ dp[triangle.size()-1][i] = triangle.get(triangle.size()-1).get(i); } for(int i = triangle.size()-2; i >=0; i--){ for(int j = 0; j <= i; j++){ dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j); } } return dp[0][0]; } }
什么情况用动态规划
一般情况下满足下面三个条件之一就有可能适用于动态规划：
- 求最大值最小值
- 判断是否可行
- 统计方案的个数（面试中99%是用dp做）
动态规划的三点要素：
- 状态(State)： 确定动态规划的对于解决动态规划的问题十分重要，当然这需要一定的灵感。有时候一种状态不够我们需要定义两种或者多种状态来解决问题
- 方程(Function): 确定状态与状态之间的联系
- 初始化(Initial):确定状态的起点，然后根据状态方程求出最终答案
动态规划的常见类型
坐标型动态规划：
坐标型动态规划通常用于X轴(一维)，矩阵(二维)。状态常常用坐标表示，即通常定义为F[i]，F[i][j]，表示从原点到当前位置。
典型的坐标型动态规划， 状态f[i][j]表示从原点到当前位置的minimum path sum。
public class Solution {
public int minPathSum(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int[][] f = new int[grid.length][grid[0].length];
f[0][0] = grid[0][0];
for(int i = 1; i < grid.length; i++){
f[i][0] = f[i-1][0] + grid[i][0];
}
for(int j = 1; j < grid[0].length; j++){
f[0][j] = f[0][j-1] + grid[0][j];
}
for(int i = 1; i < grid.length; i++){
for(int j = 1; j < grid[0].length; j++){
f[i][j] = Math.min(f[i-1][j],f[i][j-1])+grid[i][j];
}
}
return f[grid.length-1][grid[0].length-1];
}
}
F[i][j]表示从原点到当前位置的的unqiue paths,此题可以优化成滚动数组。
public class Solution {
public int uniquePaths(int m, int n) {
if(m < 0 || n < 0) return 0;
int[][] f = new int[2][n+1];
for(int j = 0; j < n; j++){
f[0][j] = 1;
}
f[1][0] = 1;
for(int i = 1; i <m; i++){
for(int j = 1; j <n; j++){
f[i%2][j] = f[(i-1)%2][j] + f[i%2][j-1];
}
}
return f[(m-1)%2][n-1];
}
}
F[i][j]表示从原点到当前位置的unique paths。
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[][] f = new int[m][n];
for(int i = 0; i < m; i++){
if(obstacleGrid[i][0] == 1) break;
f[i][0] = 1;
}
for(int j = 0; j < n; j++){
if(obstacleGrid[0][j] == 1) break;
f[0][j] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 0){
f[i][j] = f[i-1][j] + f[i][j-1];
}
}
}
return f[m-1][n-1];
}
}
序列型动态规划：
F[i]表示跳到第i步的方法总数，也可以优化成滚动数组
public class Solution {
public int climbStairs(int n) {
if(n <= 0) return 0;
if(n == 1) return 1;
int[] f = new int[n+1];
f[0] = 1;
f[1] = 1;
for(int i = 2; i <= n; i++){
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
}
Leetcode 96 Unique Binary Search Trees
dp[i]表示的是有i个点时，二叉树的个数
public class Solution {
public int numTrees(int n) {
if(n < 0) return 0;
int[] dp = new int[n+1];
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}
Leetcode 121 Best Time to Buy and Sell Stock
这题的状态Min[i]表示的到当前的最小值，也可优化成滚动数组。
public class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0) return 0;
if(prices.length == 1) return 0;
int max = 0;
int[] min = new int[prices.length];
min[0] = prices[0];
for(int i = 1; i < prices.length; i++){
min[i] = Integer.MAX_VALUE;
max = Math.max(max, prices[i]-min[i-1]);
min[i] = Math.min(min[i-1],prices[i]);
}
return max;
}
}
F[i]表示的是前面有i个字符，而不是表示第i个字符，这也导致我们定义数组长度时定义成字符串长度＋1
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if(s.isEmpty() || wordDict.isEmpty()) return false;
boolean[] f = new boolean[s.length()+1];
f[0] = true;
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <=i; j++){
String word = s.substring(i-j,i);
if(wordDict.contains(word)){
if(f[i-j]){
f[i] = true;
}
}
}
}
return f[s.length()];
}
}
F[i]表示有i＋1个房子能偷到的最大财产
public class Solution {
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[] f = new int[nums.length];
f[0] = nums[0];
f[1] = Math.max(nums[0],nums[1]);
for(int i = 2; i < nums.length; i++){
f[i] = Math.max(f[i-1],f[i-2]+nums[i]);
}
return f[nums.length-1];
}
}
这一题一开始我的状态方程是dp[i] = Math.min(dp[i],dp[k]+dp[i-k])。 但其实这是不对的，比如dp[4] = 1 != dp[2]+dp[2].
public class Solution {
public int numSquares(int n) {
if(n <= 0) return 0;
int[] dp = new int[n+1];
dp[0] = 0;
for(int i = 1; i <= n; i++){
dp[i] =Integer.MAX_VALUE;
for(int j = 1; j * j <= i; j++){
dp[i] = Math.min(dp[i],dp[i-j*j]+1);
}
}
return dp[n];
}
}
F[i]表示第i个数有几个1
public class Solution {
public int[] countBits(int num) {
if(num < 0) return null;
int[] f = new int[num+1];
f[0] = 0;
for(int i = 1; i<= num; i++){
if(i%2 == 0) f[i] = f[i/2];
if(i%2 == 1) f[i] = f[i/2]+1;
}
return f;
}
}
双序列动态规划：
10. Regular Expression Matching
典型的双序列动态规划，dp[i][j]表示字符串S的前i个字符和P的前j个字符是否匹配。
但是需要考虑如何初始化，一般需要初始化的地方是dp进行不下去的地方，本题中为dp[0][j],dp[[i][0]，但显然dp[i][0]＝false
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp= new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for(int i = 0; i < s.length(); i++){
for(int j = 0; j < p.length(); j++){
if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
dp[i+1][j+1] = dp[i][j];
}
else if(p.charAt(j) == '*'){
if(j-1>=0){
if(p.charAt(j-1)!=s.charAt(i) && p.charAt(j-1) != '.'){
dp[i+1][j+1] = dp[i+1][j-1];
}
else{
dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j] || dp[i+1][j-1];
}
}
}
}
}
return dp[s.length()][p.length()];
}
}
dp[i][j]表示word1的前i个字符和word2前j个字符所需最小的edit次数
public class Solution {
public int minDistance(String word1, String word2) {
if(word1.isEmpty()) return word2.length();
if(word2.isEmpty()) return word1.length();
int[][] dp = new int[word1.length()+1][word2.length()+1];
dp[0][0] = 0;
for(int i = 0; i < word1.length(); i++){
dp[i+1][0] = i+1;
}
for(int j = 0; j < word2.length(); j++){
dp[0][j+1] = j+1;
}
for(int i = 0; i < word1.length(); i++){
for(int j = 0; j < word2.length(); j++){
if(word1.charAt(i) == word2.charAt(j)){
dp[i+1][j+1] = dp[i][j];
}
else{
dp[i+1][j+1] = Math.min(dp[i][j],Math.min(dp[i][j+1],dp[i+1][j]))+1;
}
}
}
return dp[word1.length()][word2.length()];
}
}
Leetcode 115 Distinct Subsequences
这题与上一题的区别在于我们需要固定t不动，只在s上进行操作。
public class Solution {
public int numDistinct(String s, String t) {
int[][] dp = new int[s.length()+1][t.length()+1];
for(int i = 0; i <= s.length(); i++){
dp[i][0] = 1;
}
for(int i = 0; i < s.length(); i++){
for(int j = 0; j < t.length(); j++){
if(s.charAt(i) != t.charAt(j)){
dp[i+1][j+1] = dp[i][j+1];
}
else{
dp[i+1][j+1] = dp[i][j+1] + dp[i][j];
}
}
}
return dp[s.length()][t.length()];
}
}
博弈型动态规划：
背包型动态规划：
区间型动态规划：
dp[i][j]表示第i到第j之间的最大值。
public class Solution {
public int maxCoins(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int[] balloon = new int[nums.length+2];
balloon[0] = 1;
balloon[balloon.length-1] = 1;
for(int i = 1; i < balloon.length-1; i++){
balloon[i] = nums[i-1];
}
int[][] dp = new int[balloon.length][balloon.length];
for(int i = 1; i < balloon.length-1; i++){
dp[i][i] = balloon[i-1]*balloon[i]*balloon[i+1];
}
for(int len = 1; len < nums.length; len++){
for(int i = 1; i < balloon.length-1 && i + len < balloon.length-1; i++){
int j = i+len;
for(int k = i; k <=j; k++){
dp[i][j] = Math.max(dp[i][j],dp[i][k-1] + dp[k+1][j] + balloon[i-1]*balloon[k]*balloon[j+1]);
}
}
}
return dp[1][balloon.length-2];
}
}
划分型动态规划：
这题不光了可以用dp做，也可以用Kadane's Algorithm，但其实思路是一样，dp反而更好理解
public class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int[] f = new int[nums.length];
f[0] = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
f[i] = nums[i] + (f[i-1]>0 ? f[i-1] : 0);
max = Math.max(f[i],max);
}
return max;
}
}
Leetcode 152 Maximum Product Subarray
这种情况一种状态不足以解决问题，我们需要记录f[i]第i个位置的最大值， g[i]第i个位置的最小值。
public class Solution {
public int maxProduct(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int[] f = new int[A.length];
int[] g = new int[A.length];
f[0] = A[0];
g[0] = A[0];
int res = A[0];
for (int i = 1; i < A.length; i++) {
f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
res = Math.max(res, f[i]);
}
return res;
}
}
Leetcode 123 Best Time to Buy and Sell Stock III
```
[**Leetcode 188 Best Time to Buy and Sell Stock IV**](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)
```java
mustSell[i][j] 第i天完成第j次交易，且第i天必须交易。
globalMax[i][j] 第i天完成第j次交易，但第i天不一定要交易。
public class Solution {
public int maxProfit(int k, int[] prices) {
if(k <= 0 || prices == null || prices.length == 0) return 0;
if(k >= prices.length/2){
int profit = 0;
for(int i = 1; i < prices.length; i++){
if(prices[i]-prices[i-1] > 0){
profit += prices[i]-prices[i-1];
}
}
return profit;
}
int[][] mustSell = new int[prices.length][k+1];
int[][] globalMax = new int[prices.length][k+1];
for(int i = 1; i < prices.length; i++){
int gainOrlose = prices[i]-prices[i-1];
for(int j = 1; j <= k; j++){
mustSell[i][j] = Math.max(mustSell[i-1][j], globalMax[i-1][j-1])+gainOrlose;
globalMax[i][j] = Math.max(mustSell[i][j], globalMax[i-1][j]);
}
}
return globalMax[prices.length-1][k];
}
}
记忆化搜索：
需要记忆化搜索的原因： 1.状态之间没有明显的转换关系 2.解决"aaaaaaaaaaaaaaaaa", ['a']这类的corner case。
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
if(s.isEmpty() || wordDict.isEmpty()) return new ArrayList<String>();
List<String> result = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
return wordBreakHelper(s, wordDict, map);
}
private List<String> wordBreakHelper(String s, List<String> wordDict, Map<String, List<String>> map){
List<String> list = new ArrayList<>();
if(s.isEmpty()){
list.add("");
return list;
}
if(map.containsKey(s)){
return map.get(s);
}
for(String word : wordDict){
if(s.startsWith(word)){
List<String> sub = wordBreakHelper(s.substring(word.length()), wordDict,map);
for(String str : sub){
list.add(word + (str.isEmpty() ? "" : " ") + str);
}
}
}
map.put(s, list);
return list;
}
}