动态规划总结

理论基础

复杂的问题分解为相对简单的子问题的方法。
特征包含

重叠子问题
最优子结构
无后效性

解题步骤

确定dp数组含义（通常与题目求解的内容相同）
确定状态转移方程 dp[i] = xxx
确定初始化条件 dp[0] = x;dp[1]=xx
确定循环条件（正向、负向）

注意点：

dp数组的长度
1. 通常是n+1（返回第n个，需要存在dp[n]）
2. 入参是数组的情况，长度是nums.length，返回dp[length-1]
3. 因为数组从0开始，求n状态需要dp[n]；0也是有效数据，则求dp[n-1]
是否需要引入变量j，如果i范围内的值还需要额外对比处理，就需要引入j

经典题型

70. 爬楼梯

状态转移： dp[i] = dp[i-1] + dp[i-2]
dp数组需要dp[n]所以大小为 length+1 返回dp[n]

public int climbStairs(int n) {  
    if(n == 0) return 0;  
    if(n == 1) return 1;  
    if(n == 2) return 2;  
    int[] dp = new int[n + 1];  
    dp[1] = 1;  
    dp[2] = 2;  
    for (int i = 3; i <= n; i++) {  
        dp[i] = dp[i - 1] + dp[i - 2];  
    }  
    return dp[n];  
}

198. 打家劫舍

dp数组初始化： new int[nums.length]
状态转移方程： dp[i] = max(dp[i-2] + nums[i], dp[i-1]);

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

注意点：

dp数组代表的是i家的最大金额，数组长度只有nums.length，因为有效值包含了0，所以结果在dp[length-1]中。
dp[1]是前两家的最大金额。

300. 最长递增子序列

public int lengthOfLIS(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}
	if (nums.length == 1) return 1;
	// 注意数组长度是 length
	int n = nums.length;
	int[] dp = new int[n];
	Arrays.fill(dp,1);
	int max = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				dp[i] = Math.max(dp[i], dp[j] + 1);
			}
		}
		max = Math.max(dp[i], max);
	}
	// 找到最大值
	return max;
}

注意点：

dpi代表的是必须取i的情况下的最长子序列
dpi的最长子序列有多种可能，范围是 0~(i-1)，这个范围内都需要对比一遍。所以需要引入变量j
最后返回的最长子串可能不包含i，所以取dp数组最大值

53. 最大子数组和

dpi代表i之前的最大子序和

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

322. 零钱兑换

dp数组含义：最小零钱数，容量为length+1,因为最终是需要dp[amount]
递推公式： dp[i] = min(dp[i-coins[j]]+1, dp[i])
条件约束：背包容量不能小于物品体积，且能筹出i-coin的体积
初始化： dp[0] = 0; 非0下标初始化为最大值
遍历顺序：先遍历物品或者背包都OK

public int coinChange(int[] coins, int amount) {  
    if (amount == 0) return 0;  
    int[] dp = new int[amount + 1];  
    Arrays.fill(dp, Integer.MAX_VALUE);  
    dp[0] = 0;  
    for (int i = 1; i <= amount; i++) {  
        for (int coin : coins) {  
            if (i < coin || dp[i - coin] == Integer.MAX_VALUE) {  
                continue;  
            }  
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);  
        }  
    }  
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];  
}

注意：

数组大小是amount+1
取最小值，注意初始化为max_value
不能漏了dp[i - coin] == Integer.MAX_VALUE这个条件，筹不出 i-coin的也没有意义

扩展

279. 完全平方数 f[j] = Math.min(f[j], f[j - x] + 1);

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int t = 1; t * t <= n; t++) {
            int x = t * t;
            for (int j = x; j <= n; j++) {
                f[j] = Math.min(f[j], f[j - x] + 1);
            }
        }
        return f[n];
    }
}

72. 编辑距离

数组含义： dp[i][j] word1的前i个字符变为word2的前j个字符最小编辑距离
递推公式：

如果最后一个字符相等，只要看前i-1与j-1个字符

如果最后一个字符不等，需要取min(增、删、改)最小的值，增删改都是一步操作
初始化：二维数组的初始化，word1和word2为空字符串的时候，使用对方的长度
遍历顺序：二维数组，从前往后遍历

public int minDistance(String word1, String word2) {

        if (word1.length() == 0 || word2.length() == 0) {
            return word1.length() + word2.length();
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) +1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

注意点：

二维数组长度是 length+1 代表前n个字符。
判断第n（charAt(n-1)）个字符是否相等
二维数组的初始化 i0,0j的初始化逻辑

1143. 最长公共子序列

最长公共子序列问题，两个字符串，需要二维数组，代表text1前i个序列与text2前j个序列最长公共子序列。

如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。

如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
当 i 或 j 为 0 时，dp[i][j] 应该为 0，因为一个空字符串与任何字符串的最长公共子序列长度都是 0。

public int longestCommonSubsequence(String text1, String text2) {
	int m = text1.length();
	int n = text2.length();
	int[][] dp = new int[m + 1][n + 1];

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			} else {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[m][n];
}

扩展：

718. 最长重复子数组 dp[i][j]=dp[i-1][j-1]+1;
647. 回文子串 `状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串；状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false。注意递归顺序

647. 回文子串

dp二维数组代表字符i~j范围能是否是回文
递推公式：当(s[i]==s[j])时：

i==j || i+1==j也是回文

j-i>2 需要判断 dp[i+1][j-1]是否是回文
注意因为是左下方推导出右上方，所以先遍历j在遍历i保证做下方数据先存在。

public int countSubstrings(String s) {  
    if (s == null || s.length() == 0) return 0;  
    int n = s.length();  
    boolean[][] dp = new boolean[n][n];  
    // s[i] == s[j]  && dp[i][j] = dp[i+1][j-1]  
    int result = 0;  
    for (int j = 0; j < n; j++) {  
        for (int i = 0; i <= j; i++) {  
            if (s.charAt(i) == s.charAt(j)) {  
                if (j - i < 2) {  
                    dp[i][j] = true;  
                    result++;  
                } else if (dp[i + 1][j - 1]) {  
                    dp[i][j] = true;  
                    result++;  
                }  
            }  
        }  
    }  
    return result;  
}

714. 买卖股票的最佳时机含手续费

dp[i][0]不持有股票，dp[i][1]持有股票。

public int maxProfit(int[] prices, int fee) {
	int n = prices.length;
	int[][] dp = new int[n][2];
	dp[0][0] = 0;
	dp[0][1] = -prices[0];
	for (int i = 1; i < n; ++i) {
		dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
		dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
	}
	return dp[n - 1][0];
}

62. 不同路径

两个维度，二维数组。dp[i][j]代表路径方法总和。求的是mn维，结果是在dp[m-1][n-1]中的（从0开始的）。
状态转移： dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化：二维数组初始化都是初始化第一行与第一列。

public int uniquePaths(int m, int n) {
	int[][] f = new int[m][n];
	for (int i = 0; i < m; ++i) {
		f[i][0] = 1;
	}
	for (int j = 0; j < n; ++j) {
		f[0][j] = 1;
	}
	for (int i = 1; i < m; ++i) {
		for (int j = 1; j < n; ++j) {
			f[i][j] = f[i - 1][j] + f[i][j - 1];
		}
	}
	return f[m - 1][n - 1];
}

扩展：

64. 最小路径和 p[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]

背包问题

01背包

二维dp数组解法
dp数组代表 0~i之间的物品任取，放进容量为j的背包

public static int knapsack(int[] weight, int[] value, int capacity) {  
    int n = weight.length;  
    // 二维数组，列代表的是物品， 行代表的是容量  
    int[][] dp = new int[n][capacity + 1];  
    // 初始化  
    // 第一列全部初始化为0 因为背包容量j=0 ，所以不会有价值  
    for (int i = 0; i < n; i++) {  
        dp[i][0] = 0;  
    }  
    // 第一行，只要容量大于第一个物品0 则价值就是物品0的价值  
    for (int j = 0; j <= capacity; j++) {  
        if (j >= weight[0]) {  
            dp[0][j] = value[0];  
        }  
    }  
    for (int i = 1; i < n; i++) {  
        for (int j = 1; j <= capacity; j++) {  
            if (weight[i] <= j) {  
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);  
            } else {  
                dp[i][j] = dp[i - 1][j];  
            }  
        }  
    }  
    return dp[n - 1][capacity];  
}

完全背包

public class CompleteKnapsack {
    public static int completeKnapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length; // 物品的数量
        int[] dp = new int[capacity + 1]; // 动态规划数组
        // 初始化动态规划数组
        for (int w = 0; w <= capacity; w++) {
            dp[w] = 0;
        }
        // 填充动态规划数组
        for (int i = 0; i < n; i++) {
            for (int w = weights[i]; w <= capacity; w++) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        // 返回最大价值
        return dp[capacity];
    }

    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5}; // 物品的重量
        int[] values = {3, 4, 5, 6}; // 物品的价值
        int capacity = 8; // 背包的容量
        int maxValue = completeKnapsack(weights, values, capacity);
        System.out.println("最大价值为: " + maxValue);
    }
}