动态规划（Dynamic Programming），即动态递推。
1. 递归 + 记忆化 -> 递推
2. 状态的定义：opt[n]，dp[n]，fib[n]
3. 状态转移方程：opt[n] = best_of(opt[n-1], opt[n-2], ...)
4. 最优子结构
DP vs 回溯 vs 贪心
回溯（递归）—重复计算
贪心—永远局部最优
DP—记录局部最优子结构 / 多种记录值
思路：本题是斐波那契数列的应用。
class Solution { public int climbStairs(int n) { /*if (n <= 2) return n; int n1 = 1; int n2 = 2; for (int i = 3; i <= n; i++) { n2 = n2 + n1; n1 = n2 - n1; } return n2;*/ // 写成动态规划的递推形式 if (n <= 2) return n; 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]; } }
思路：本题是DP的经典题目。需要自底向上开始递推，首先定义DP的状态，然后推出DP方程。
优化：使用一维数组而不是二维数组，这样只使用了O(n)的额外空间。
class Solution { public int minimumTotal(List<List<Integer>> triangle) { // 方法1： 时间复杂度和空间复杂度 都是O(n^2) /*int n = triangle.size(); // 1. 状态的定义：dp[i][j]表示从点(i,j)到底边的最小路径和 int[][] dp = new int[n + 1][n + 1]; // 从三角形的最后一行开始递推。 for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // 2. 状态转移方程 dp[i][j] = Math.min(dp[i + 1][j],dp[i + 1][j + 1]) + triangle.get(i).get(j); } } return dp[0][0];*/ // 由于递推中，计算dp[i][j]时，只用到了下一行的dp[i+1][j]和dp[i+1][j+1]。 // 而不需要记录整个层的结果，因此dp数组不需要定义N行，只需要一行即可。 // 方法2：进行空间优化，仅使用一维数组. 时间复杂度O(n^2)，空间复杂度O(n) int n = triangle.size(); int[] dp = new int[n + 1]; for (int i = n - 1; 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]; } }
思路：DP。关键点在于：由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin。
视频：覃超P47
class Solution { public int maxProduct(int[] nums) { int max = Integer.MIN_VALUE; int imax = 1, imin = 1; for (int i = 0; i < nums.length; i++) { // 由于存在负数，那么会导致最大的变最小的，最小的变最大的。 // 当负数出现时则imax与imin进行交换再进行下一步计算 if (nums[i] < 0){ int temp = imax; imax = imin; imin = temp; } imax = Math.max(imax * nums[i], nums[i]); imin = Math.min(imin * nums[i], nums[i]); max = Math.max(max,imax); } return max; } }
题目描述：
分析：前四个属于一类问题，LC121相当于K=1的情况；LC122相当于K为无穷的情况；LC123相当于K=2的情况；LC188属于一般情况（三维动态规划）
参考：
class Solution121 { public int maxProfit(int[] prices) { // DP写法1：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格} if (prices == null || prices.length == 0) return 0; int min = prices[0]; int profit = 0; for (int i = 1; i < prices.length; i++) { profit = Math.max(profit, prices[i] - min); min = Math.min(min, prices[i]); } return profit; // DP此类问题的通用写法： /*if (prices == null || prices.length == 0) return 0; int len = prices.length; int[][] dp = new int[len][2]; dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < len; i++) { dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); dp[i][1] = Math.max(dp[i-1][1],-prices[i]);// 注意与122题对比，只允许交易一次，因此手上的现金数就是当天的股价的相反数 } return dp[len-1][0];*/ // 对上述代码进行空间优化 /*if (prices == null || prices.length == 0) return 0; int dp0 = 0, dp1 = -prices[0]; for (int i = 1; i < prices.length; i++) { dp0 = Math.max(dp0,dp1+prices[i]); dp1 = Math.max(dp1,-prices[i]); } return dp0;*/ } }
class Solution122 { public int maxProfit(int[] prices) { /** * 方法1：贪心（针对此问题的特殊解法，因为一天可以买卖无数次） * 当天卖出后，当天还可以买入。只要今天比昨天大，就卖出 */ int res = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]){ res += prices[i] - prices[i-1]; } } return res; /** * 方法2.1 ： 动态规划 * 不能同时参与多笔交易，所以每天交易结束后只有持有一支股票和没有持有两种状态。 * dp[i][0]表示第i天交易完成后没有持股的最大利润 * dp[i][1] 表示第i天交易完成后持股的最大利润. * 第一种dp[i][0]，说明第i天没有持股，此时有两种可能，前一天没有持股，今天也不买。或者前一天持股，在今天卖出。 * 第二种dp[i][1],说明第i天持有股票，此时有两种可能，前一天持股，今天保持不动。或者前一天没有持股，今天买入。 */ // int len = prices.length; // int[][] dp = new int[len][2]; // dp[0][0] = 0; // dp[0][1] = -prices[0]; // for (int i = 1; i < len; i++) { // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // } // return dp[len - 1][0]; /** * 方法2.2：动态规划 * 由于今天的利润只和前一天相关，我们只需要记录前一天的利润。因此可以进行空间优化。 */ // int len = prices.length; // int dp0 = 0, dp1 = -prices[0]; // for (int i = 1; i < len; i++) { // int newDp0 = Math.max(dp0,dp1 + prices[i]); // int newDp1 = Math.max(dp1,dp0 - prices[i]); // dp0 = newDp0; // dp1 = newDp1; // } // return dp0; } }
class Solution123 { public int maxProfit(int[] prices) { /** * 针对此类问题的通用写法： * 注： 规定一次交易产生是在 【买入股票】 的时候，即买入股票时交易次数加1 */ /*if (prices == null || prices.length == 0) return 0; int len = prices.length; // 第 2 维的 0 没有意义，1 表示交易进行了 1 次，2 表示交易进行了 2 次 int[][][] dp = new int[len][3][2]; dp[0][1][1] = -prices[0]; dp[0][2][1] = Integer.MIN_VALUE; //注意不能初始化为0 for (int i = 1; i < len; i++) { // 转移顺序先持股，再卖出 dp[i][1][1] = Math.max(dp[i-1][1][1], -prices[i]); dp[i][1][0] = Math.max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]); dp[i][2][1] = Math.max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]); dp[i][2][0] = Math.max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]); } return Math.max(dp[len-1][1][0],dp[len-1][2][0]);*/ /** * 对上述代码进行空间优化 * 由于今天只参考了昨天的状态，所以直接去掉第一维不会影响状态转移的正确性 */ /*if (prices == null || prices.length == 0) return 0; int[][] dp = new int[3][2]; dp[1][1] = -prices[0]; dp[2][1] = Integer.MIN_VALUE; for (int i = 1; i < prices.length; i++) { dp[1][1] = Math.max(dp[1][1], -prices[i]); dp[1][0] = Math.max(dp[1][0], dp[1][1] + prices[i]); dp[2][1] = Math.max(dp[2][1], dp[1][0] - prices[i]); dp[2][0] = Math.max(dp[2][0], dp[2][1] + prices[i]); } return dp[2][0];*/ // 收益值(dp[2][0] >= dp[1][0]) /** * 针对本题的变量写法： * buy1:第一次买入股票可获得的最大收益 * sell1:第一次卖出股票可获得的最大收益 */ if (prices == null || prices.length == 0) return 0; int buy1 = -prices[0], buy2 = Integer.MIN_VALUE; int sell1 = 0, sell2 = 0; for (int i = 1; i < prices.length; i++) { buy1 = Math.max(buy1, -prices[i]); sell1 = Math.max(sell1, buy1 + prices[i]); buy2 = Math.max(buy2, sell1 - prices[i]); sell2 = Math.max(sell2, buy2 + prices[i]); } return sell2; } }
class Solution188 { public int maxProfit(int k, int[] prices) { /** * 最一般的情况，相当于122题(K为无穷) 和 123题(K=2) 的融合。 * 如果k超过一个临界值，最大收益就不再取决于最大交易次数，而是取决于数组的长度 * 一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。 * 如果数组长度为 n，则有收益的交易的数量最多为 n/2 ，因此如果k>=n/2，等价于k为无穷的情况。 */ if (prices == null || prices.length == 0) return 0; int len = prices.length; if (k >= len/2){ return greedy(prices); } int[][] dp = new int[k+1][2]; for (int kk = 1; kk <= k; kk++) { dp[kk][1] = -prices[0]; } for (int i = 1; i < len; i++) { for (int kk = 1; kk <= k; kk++) { dp[kk][1] = Math.max(dp[kk][1], dp[kk-1][0] - prices[i]); dp[kk][0] = Math.max(dp[kk][0], dp[kk][1] + prices[i]); } } return dp[k][0]; } // 相当于k为无穷的情况，LeetCode 122 public int greedy(int[] prices) { int res = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] - prices[i-1] > 0){ res += prices[i] - prices[i-1]; } } return res; // 使用DP /*int[][] dp = new int[prices.length][2]; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[prices.length - 1][0];*/ } }
class Solution309 { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) return 0; int len = prices.length; // 定义三个状态： 注意定义的状态是第i天结束后的状态 // 1：持股; 0：不持股且不是冷冻期; 2：冷冻期(今天卖出,不持股) int[][] dp = new int[len][3]; dp[0][1] = -prices[0]; for (int i = 1; i < len; i++) { dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); dp[i][2] = dp[i-1][1] + prices[i]; dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]); } return Math.max(dp[len-1][0], dp[len-1][2]); // 空间优化 /*int dp1 = -prices[0]; int dp0 = 0, dp2 = 0; for (int i = 1; i < len; i++) { int newDp1 = Math.max(dp1, dp0 - prices[i]); int newDp2 = dp1 + prices[i]; int newDp0 = Math.max(dp0, dp2); dp0 = newDp0; dp1 = newDp1; dp2 = newDp2; } return Math.max(dp0,dp2);*/ } }
class Solution714 { public int maxProfit(int[] prices, int fee) { // 与122题类似，只是多了手续费 if (prices == null || prices.length == 0) return 0; int len = prices.length; int[][] dp = new int[len][2]; dp[0][1] = -prices[0] - fee; for (int i = 1; i < len; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i] - fee); } return dp[len-1][0]; /*int dp0 = 0, dp1 = -prices[0] - fee; for (int i = 1; i < len; i++) { int newDp0 = Math.max(dp0, dp1 + prices[i]); int newDp1 = Math.max(dp1, dp0 - prices[i] - fee); dp0 = newDp0; dp1 = newDp1; } return dp0;*/ } }
Note：该题为不连续的情况，可以延伸到最长连续子序列长度该怎么求。 另外，除了要会求子序列的长度，还要会求出最长的子序列是什么。
方法1：DP----O(n^2)
方法2：二分-------O(nlogn)。 不是很理解二分的过程 T_T
class Solution { public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; /** * 方法1：动态规划，时间复杂度O(n^2) */ // 1.状态定义： dp[i]状态表示从开始到第i个元素结尾(包含第i个元素)，最长子序列的长度 // 2.DP方程： dp[i] = max{dp[j] + 1} ( j<i, nums[j]<nums[i] ) /*int[] dp = new int[nums.length]; int res = 1; for (int i = 0; i < nums.length; i++) { dp[i] = 1; // 初始化。如果0到i-1中所有的数都不比第i个数小，则单独一个数是子序列 for (int j = 0; j < i; j++) { if (nums[j] < nums[i]){ // 以哪个数结尾的最大递增子序列更大，就选其作为倒数第二个数 dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); // 所有dp[i]中找最大的 } return res;*/ /** * 方法2：二分查找，时间复杂度O(nlogn) * a.直接维护最长子序列数组res[]，注意该数组是有序的 * 1)如果当前元素比结果数组的值都大，就追加在结果数组的尾部(相当于递增序列长度加1) * 2)否则，用当前元素覆盖掉第一个比它大的元素(比它大的元素中最小的那个)。 这样就能给后面数机会 * b.返回数组的长度 * 说明：由于每个数O(n)找到其要插入的位置用的是二分查找O(logn)，所以总体是O(nlogn)的。 * 2)中的覆盖操作可能会导致最终的结果数组并不是最终的递增序列，但对长度无影响。 * 举个例子:[10,11,12,13,1,2,3,4,5] * ->[10,11,12,13]->[1,11,12,13]->[1,2,12,13] ....-> [1,2,3,4,5] */ int[] res = new int[nums.length]; int len = 0; // res当前的长度 for (int num : nums){ int start = 0, end = len; // 利用二分查找res数组索引为[0, len)之间元素，找到第一个大于num的元素。 while (start < end){ int mid = start + ((end - start) >> 1); if (res[mid] < num){ start = mid + 1; }else { end = mid; } } res[start] = num; if (start == len){ // 说明区间中不存在比num大的数+ len++; } // 调二分API /*int idx = Arrays.binarySearch(res,0,len,num); idx = idx < 0 ? -idx - 1 : idx; res[idx] = num; if (idx == len) len++;*/ } return len; } }
【拓展】：如何根据dp数组得到最长递增子序列是什么？------>参考左神P203
public int[] generateLIS(int[] arr, int[] dp) { int len = 0; int index = 0; for (int i = 0; i < dp.length; i++) { if (dp[i] > len){ len = dp[i]; index = i; } } int[] lis = new int[len]; lis[--len] = arr[index]; for (int i = index; i >= 0; i--) { if (arr[i] < arr[index] && dp[i] == dp[index] - 1) { lis[--len] = arr[i]; index = i; } } return lis; }
思路：转换成 “跳台阶” 问题。
class Solution { /** * 思路； 转化为跳台阶问题 * 1. 状态的定义： dp[i] 表示到i台阶时的最小步数, 也即凑齐i需要的最少硬币数 * 2. 状态转移方程 dp[i] = min {dp[i-coins[j]} + 1 * 举例： [1,2,5] 11 * dp[i] = min{i-1, i-2, i-5} + 1 * dp[11] = min{dp[10],dp[9],dp[6]} + 1 */ public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; // 最多的硬币数就是全部使用面值1的硬币来换, amount+1是不可能达到的换取数量。 // 因为硬币面额最小为整数1，所以只要有解，最小硬币数必然小于amount+1 int max = amount + 1; Arrays.fill(dp, max); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (i >= coins[j]) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] == amount + 1 ? -1 : dp[amount]; } }
class Solution { /** * 1. 状态的定义：dp[i][j]：word1前i个字符 变为 word2前j个字符 所需最小操作数 * 最后返回dp[word1.length][word2.length] * 2. DP方程: 分两种情况， * 1）如果当前字母相同，则dp[i][j] = dp[i-1][j-1] * 2) 否则，取 删-增-替 的最小值 + 1， * 即 min{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]} + 1 */ public int minDistance(String word1, String word2) { int len1 = word1.length(), len2 = word2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 0; i <= len1; i++) { dp[i][0] = i; } for (int j = 0; j <= len2; j++) { dp[0][j] = j; } for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { // 注意dp数组有一个偏移，所以是 charAt(i-1)而不是i if (word1.charAt(i-1) == word2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; }else { // 分别对应 增，删，替 dp[i][j] = Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1])) + 1; } } } return dp[len1][len2]; } }
原文：https://www.cnblogs.com/HuangYJ/p/14031237.html