不知道什么是动态规划的，传送门在这儿：[干货]动态规划十问十答
动态规划进阶：动态规划：从新手到专家
相信看完上面两个链接的博客后，应该对于动态规划有一个新的认识和了解了。接下来就来看看LintCode上DP(下文我将以DP或者Dynamic Programming表示动态规划)的题目。
强烈推荐次博客，将动规分类总结做的很好：动态规划完整笔记
常见的动态规划题类型有好几种，有的动规是可以用滚动数组优化的，以下分别归类介绍：
1 坐标型动态规划题：
state: f[x]表示我从起点走到坐标x, f[x][y] 表示我从起点走到坐标x,y.... function: 研究走到x,y这个点之前的一步 initialize: 起点 answer：终点437. Copy Books
给了一些书，让几个人去拷贝，一个人只能拷贝连续的几本书（比如拷贝了第1、2、3本），但是一个人不能跳着拷贝（比如就不能拷贝第1、3本，必须得连续的拷贝才行）。每本书都有不同的页数，翻译一页需要1分钟。
给定一个包含了页数的数组，和翻译员的人数。问你最少需要多少分钟才能把这些书翻译完。
这其实是一道坐标型动态规划题，假设动态规划的方程为dp[m][n]，这就代表前m本书被前n个人拷贝所需的最少时间。接下来我们来找出动规的转移方程。为了方便起见，我们假设数组的起始index是从1开始的。
假设书的数组是[3, 2, 4]，人数K=2. 那么我们需要求的就是dp[3][2]，也就是前3本书被前2个人拷贝所需要的最少时间。我们从后往前倒推，不难得知dp[3][2]是有可能从dp[3][1],max(dp[2][1], pages[3]), max(dp[1][1], pages[2] + pages[3]) 演变而来的。但是这里面可以排除dp[3][1]，因为如果前3本书都给一个人翻译了，那第二个人就无用武之地了，所以这样的转换是无意义的。
因此我们可以得到dp[3][2]的转移方程如下：
dp[3][2] = Min(Max(dp[2][1], pages[3]), Max(dp[1][1], pages[2] + pages[3]));
而且不难得知dp[1][n] = dp[1][3] = dp[1][2] = dp[1][[1] = pages[1]; 因为5个人翻译1本书跟1个人翻译一本书的时间是一样的，剩下的4个人没有用武之地，所以毫无意义。
也不难得知dp[n][1] = pages[1] + pages[2] + ... + pages[n]; 因为一个人翻译n本书的时间等于n本书的页数之和。
所以以上两个“不难得知”可以用于初始化dp方程。
我们把dp方程generalize一下如下所示：
DP[m][n] = MIN( MAX(DP[m-1][n-1], pages[m]), MAX(DP[m-2][n-1], pages[m-1]+pages[m]), ... , MAX(DP[1][n-1], pages[2]+pages[3]+...+pages[m]) );
数组长度是N，人数是K，则时间复杂度是O(N * N * K)
public class Solution { /** * @param pages: an array of integers * @param k: an integer * @return: an integer */ public int calSum(int[] sum, int startIndex, int endIndex) { return sum[endIndex] - sum[startIndex]; } public int copyBooks(int[] pages, int k) { if (pages == null || pages.length <= 0 || k < 1) { return 0; } int[][] f = new int[pages.length + 1][k + 1]; int[] sum = new int[pages.length + 1]; sum[0] = 0; // initialization f[0][0] = f[1][0] = f[0][1] = 0; f[1][1] = pages[0]; for (int i = 1; i < f.length; i++) { f[i][1] = pages[i - 1] + f[i - 1][1]; sum[i] = sum[i - 1] + pages[i - 1]; } for (int i = 1; i < f[0].length; i++) { f[1][i] = f[1][1]; } // DP function for (int i = 2; i <= pages.length; i++) { for (int j = 2; j <= k; j++) { f[i][j] = Integer.MAX_VALUE; for (int x = 1; x <= i - 1; x++) { int result = Math.max(f[x][j - 1], calSum(sum, x, i)); f[i][j] = Math.min(result, f[i][j]); } } } // result return f[pages.length][k]; } }
438. Copy Books II
上一道题的变种，还是一个人只能翻译连续的几本书，不过数组变成了每个人翻译一本书所需要的时间了。
Given n books( the page number of each book is the same) and an array of integer with size k means k people to copy the book and the i th integer is the time i th person to copy one book). You must distribute the continuous id books to one people to copy. (You can give book A[1],A[2] to one people, but you cannot give book A[1], A[3] to one people, because book A[1] and A[3] is not continuous.) Return the number of smallest minutes need to copy all the books.
Given n = 4, array A = [3,2,4], .
Return 4( First person spends 3 minutes to copy book 1, Second person spends 4 minutes to copy book 2 and 3, Third person spends 4 minutes to copy book 4. )
我们用dp[i][j]表示前i本书被前j个人copy所需要的最小时间。假设的数组是[3, 2, 4]，书本数K=4. 那么我们需要求的就是dp[4][3]，也就是前4本书被前3个人拷贝所需要的最少时间。我们从后往前倒推，不难得知dp[4][3]是有可能从dp[4][2],max(dp[3][2], arr[3] * 1), max(dp[2][2], arr[3] * 2), max(dp[1][2], arr[3] * 3), max(dp[0][2], arr[3] * 4)演变而来的。不难得知，dp[1][1] = arr[1] * 1, dp[2][1] = arr[1] * 2, dp[n][1] = arr[1] * n
我们把dp方程generalize一下如下所示：
DP[m][n] = MIN( MAX(DP[m][n-1], arr[n] * 0), MAX(DP[m-1][n-1], arr[n] * 1), ... , MAX(DP[0][n-1], arr[n] * m) );
需要注意的是，如果发现arr[n] * m 已经大于DP[k][n-1]的时候，就不用再继续往下循环了，以此可以减少运行时间。然后还可以用滚动数组来优化空间复杂度。
public int copyBooksII(int n, int[] times) { return copyBooksWithRollingArray(n, times); } public int copyBooksWithRollingArray(int n, int[] times) { int len = times.length; // state int[][] dp = new int[n + 1][2]; // initialize for (int i = 0; i <= n; i++) { dp[i][0] = times[0] * i; } // dp function for (int j = 1; j < len; j++) { for (int i = 1; i <= n; i++) { int a = j % 2; int b = 1 - a; dp[i][a] = Integer.MAX_VALUE; for (int k = 0; k <= i; k++) { int tmp = Math.max(dp[i-k][b], times[j] * k); dp[i][a] = Math.min(tmp, dp[i][a]); if (dp[i-k][b] <= times[j] * k) { break; } } } } // result return dp[n][(len-1)%2]; } public int copyBooksII2D(int n, int[] times) { int len = times.length; // state int[][] dp = new int[n + 1][len + 1]; // initialize for (int i = 0; i <= n; i++) { dp[i][1] = times[0] * i; } // dp function for (int i = 1; i <= n; i++) { for (int j = 2; j <= len; j++) { dp[i][j] = Integer.MAX_VALUE; for (int k = 0; k <= i; k++) { int tmp = Math.max(dp[i-k][j-1], times[j-1] * k); dp[i][j] = Math.min(tmp, dp[i][j]); if (dp[i-k][j-1] <= times[j-1] * k) { break; } } } } // result return dp[n][len]; }436. Maximal Square
这是一道二维坐标型动态规划。思路： 分析大问题的结果与小问题的相关性 f[i][j] 表示以i和j作为正方形的右下角可以扩展的最大边长
eg： 1 1 1 1 1 1 1 1 1 (traget)
traget 的值与3部分相关：
1. 青蓝色的正方形部分 f[i - 1][j - 1] 2. 紫粉红色 target上面的数组 up[i - 1][j] 即target上面的点 往上延伸能达到的最大长度 3. 红色的target左边的数组 left[i][j - 1] 如果 target ＝＝ 1 f[i][j] = min (left[i][j - 1], up[i - 1][j], f[i - 1][j - 1]) + 1; 对于left和up数组 可以在intialization的时候用o(n^2)扫描整个矩阵实现！
优化思路1: 因为 f[i - 1][j] = left[i - 1][j] f[i][j - 1] = up[i][j - 1] 这样 不需要额外的建立left和up数组 if (target == 1) f[i][j] = min (f[i - 1][j - 1], f[i][j - 1],f[i - 1][j]) + 1;
public int maxSquare(int[][] matrix) { int ans = 0; if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return ans; } int n = matrix.length; int m = matrix[0].length; // 状态 int[][] f = new int[n][m]; // 初始化 for (int i = 0; i < n; i++) { f[i][0] = matrix[i][0]; ans = Math.max(f[i][0], ans); } for (int i = 0; i < m; i++) { f[0][i] = matrix[0][i]; ans = Math.max(f[0][i], ans); } // 方程 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (matrix[i][j] == 1) { f[i][j] = Math.min(Math.min(f[i-1][j-1], f[i][j-1]), f[i-1][j]) + 1; } else { f[i][j] = 0; } ans = Math.max(ans, f[i][j]); } } // 结果 return ans * ans; } 优化思路2: 由于f[i][j]只和前3个结果相关 f[i - 1][j - 1] f[i][j - 1] f[i - 1][j] f[i][j] 故只需要保留一个2行的数组！！！ 列上不能优化，因为2重循环的时候 下列的时候依赖于上列的结果，上列的结果需要保存到计算下列的时候用。 只能在行上滚动，不能行列同时滚动！！！ －－－－－－－－－－－－－－－－－－－－ state： f[i][j] 表示以i和j作为正方形右下角可以扩展的最大边长 function: if matrix[i][j] == 1 f[i % 2][j] = min(f[(i - 1) % 2 ][j], f[(i - 1) % 2][j - 1], f[i％2][j - 1]) + 1; initialization: f[i%2][0] = matrix[i][0] f[0][j] = matrix[0][j] answer: max{f[i%2][j]} public int maxSquare_rollingArray(int[][] matrix) { int ans = 0; if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return ans; } int n = 2; int m = matrix[0].length; // 状态 int[][] f = new int[n][m]; // 初始化 for (int i = 0; i < n; i++) { f[i][0] = matrix[i][0]; ans = Math.max(f[i][0], ans); } for (int i = 0; i < m; i++) { f[0][i] = matrix[0][i]; ans = Math.max(f[0][i], ans); } // 方程 for (int i = 1; i < matrix.length; i++) { for (int j = 1; j < m; j++) { if (matrix[i][j] == 1) { f[i%2][j] = Math.min(Math.min(f[(i-1)%2][j-1], f[i%2][j-1]), f[(i-1)%2][j]) + 1; } else { f[i%2][j] = 0; } ans = Math.max(ans, f[i%2][j]); } } // 结果 return ans * ans; } 631. Maximal Square II求最大的正方形的面积，这个正方形要满足对角线为1，其他地方全是0。问能不能找到这样的正方形。
dp[m][n]表示以matrix[m][n]为右下角的最大的正方形的边长。up[m][n]代表紧挨着matrix[m][n]上面有多少个连续的0。left[m][n]代表紧挨着matrix[m][n]左边多少个连续的0。那么不难得知如下的状态转移方程：
if matrix[m][n] == 1: dp[m][n] = MIN ( dp[m-1][n-1], left[m][n-1], up[m-1][n] ) + 1 left[m][n] = 0; up[m][n] = 0; else: dp[m][n] = 0; if (left[m][n-1] > 0) { left[m][n] = left[m][n-1] + 1; } else { left[m][n] = 1; } if (up[m-1][n] > 0) { up[m][n] = up[m-1][n] + 1; } else { up[m][n] = 1; } 代码如下：
public int maxSquare2(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; } int n = matrix.length; int m = matrix[0].length; int[][] dp = new int[n][m]; int[][] left = new int[n][m]; int[][] up = new int[n][m]; // initialization for (int i = 0; i < n; i++) { left[i][0] = (matrix[i][0] == 0) ? 1 : 0; dp[i][0] = (matrix[i][0] == 1) ? 1 : 0; } for (int i = 0; i < m; i++) { up[0][i] = (matrix[0][i] == 0) ? 1 : 0; dp[0][i] = (matrix[0][i] == 1) ? 1 : 0; } // result int result = dp[0][0]; // state function for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (matrix[i][j] == 1) { dp[i][j] = Math.min(Math.min(dp[i-1][j-1], left[i][j-1]), up[i-1][j]) + 1; left[i][j] = 0; up[i][j] = 0; } else { dp[i][j] = 0; if (left[i][j-1] > 0) { left[i][j] = left[i][j-1] + 1; } else { left[i][j] = 1; } if (up[i-1][j] > 0) { up[i][j] = up[i-1][j] + 1; } else { up[i][j] = 1; } } result = Math.max(result, dp[i][j]); } } return result * result; }76. Longest Increasing Subsequence
最长递增的子序列，这道题让我们求最长递增子串Longest Increasing Subsequence的长度，简称LIS的长度。
我们用dp[i]表示以坐标i为结尾的子串的最大长度。我们维护一个一维dp数组，其中dp[i]表示以nums[i]为结尾的最长递增子串的长度，对于每一个nums[i]，我们从第一个数再搜索到i，如果发现某个数小于nums[i]，我们更新dp[i]，更新方法为dp[i] = max(dp[i], dp[j] + 1)，即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小，我们就这样不断的更新dp数组，到最后dp数组中最大的值就是我们要返回的LIS的长度。那么dp[i] = max(dp[i], dp[j] + 1).
public int longestIncreasingSubsequence(int[] nums) { // state int[] dp = new int [nums.length]; // intialize for (int i = 0; i < nums.length; i++) { dp[i] = 1; } // dp function for (int i = 0; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[j] + 1, dp[i]); } } } // result int res = 0; for (int i = 0; i < nums.length; i++) { res = Math.max(res, dp[i]); } return res; }
2 序列型动态规划题：
state: f[i]表示前i个位置／数字／字符， 第i个... function: f[i] = f[j]... j是i之前的一个位置 initialize: f[0]... answer: f[n]... 一般answer是f(n)而不是f(n - 1) 因为对于n个最富，包含前0个字符(空串)，前1个字符...前n个字符。 注意： 如果不是跟坐标相关的动态规划，一般有n个数／字符，就开n＋1个位置的数组。 第0个位置单独留出来作初始化
392. House Robber
有一条街上有一些商店，每个商店里都有一定数量的钱，让你去抢劫，但是你不能抢相邻的两个店，比如你不能抢第1、2个店，但是你可以抢第1、3个店或者第1、4个店。反正就是店不能挨着。然后问你从街头到尾一路抢过去最多能抢多少钱。商店和钱是以数组的形式给出来的。比如给定数组[3, 8, 4] 问你最多能抢多少钱。其实想出动规方程就很简单了。dp[i]代表前i个商店最多能抢多少钱。dp[i] = MAX(dp[i-1], dp[i-2] + A[i])。
public long withoutRollingArray(int[] A) { if (A == null || A.length == 0) { return 0; } if (A.length == 1) { return A[0]; } long[] f = new long[A.length + 1]; f[0] = 0; f[1] = A[0]; for (int i = 2; i < f.length; i++) { f[i] = Math.max(f[i - 2] + A[i - 1], f[i - 1]); } return f[f.length - 1]; }仔细观察下，这道题能不能把空间复杂度优化一下呢，我们用到了一个长度N的数组去存储各个状态。但是其实我们并不需要把每个状态都存下来。所以我们可以用滚动数组rolling array去优化。数组的长度只需要为2就行。这样空间复杂度就优化到了O(1)： public long withRollingArray(int[] A) { // corner cases if (A == null || A.length == 0) { return 0; } if (A.length == 1) { return A[0]; } // state int n = A.length; long[] f = new long[2]; // initialization f[0] = 0; f[1] = A[0]; // function for (int i = 2; i <= n; i++) { f[i%2] = Math.max(f[(i-2)%2]+A[i-1], f[(i-1)%2]); } // result return f[n%2]; } 534. House Robber II是上一道题的变种，一条直线的街道变成了环形街道，第一个店铺跟最后一个店铺相邻了。其他规则不变。可以考虑把环形街道拆分成两个数组，一个数组去掉第一个店铺，一个数组去掉最后一个店铺。分别对这2个数组应用上一题的代码，然后取2个结果的较大值就可以了：
public int houseRobber1(int[] nums) { if (nums == null || nums.length <= 0) { return 0; } if (nums.length == 1) { return nums[0]; } int size = nums.length; int[] f = new int[size]; f[0] = nums[0]; f[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < size; i++) { f[i] = Math.max(f[i-1], f[i-2]+nums[i]); } return Math.max(f[size-1], f[size-2]); } public int houseRobber2(int[] nums) { if (nums == null || nums.length <= 0) { return 0; } if (nums.length == 1) { return nums[0]; } int size = nums.length; int[] nums1 = new int[size - 1]; int[] nums2 = new int[size - 1]; for (int i = 0; i < size - 1; i++) { nums1[i] = nums[i]; } for (int i = 0; i < size - 1; i++) { nums2[i] = nums[i + 1]; } return Math.max(houseRobber1(nums1), houseRobber1(nums2)); }而House Robber III这道题也是变种，不过是一棵树了，而且方法是DFS，所以就不在DP这里面描述了。394. Coins in a Line
两个人轮流从同一边拿硬币，一次能拿1个或者2个，谁能拿到最后一个谁就是王者。问你第一个人能不能是王者。这是一道典型的博弈问题。
state: dp[i] 表示现在还剩下i个硬币，前者最后输赢状况 function： dp[n] = (!dp[n - 1]) || (!dp[n - 2]) intialize: dp[0] = false; dp[1] = true; dp[2] = true; answer: dp[n]
不难写出如下代码并AC：
public boolean dp(int n) { if (n == 0) { return false; } if (n <= 2) { return true; } boolean[] dp = new boolean[n + 1]; dp[1] = dp[2] = true; for (int i = 3; i <= n; i++) { dp[i] = (!dp[i-1] || !dp[i-2]); } return dp[n]; }仔细观察下，其实我们可以用滚动数组来优化空间复杂度： public boolean dp_rollingArray(int n) { if (n == 0 || n == 3) { return false; } if (n <= 2) { return true; } boolean[] dp = new boolean[3]; dp[0] = dp[1] = true; for (int i = 3; i < n; i++) { dp[(i-1)%3] = (!dp[(i-2)%3] || !dp[(i-3)%3]); } return dp[(n-1)%3]; }再仔细观察下，发现其实是有规律的，可以用时空复杂度均为O(1)的贪心算法： public boolean greedy(int n) { if (n % 3 == 0) { return false; } return true; }395. Coins in a Line II
还是两个人轮流从同一边拿硬币，也是一次能拿2个或者1个，谁拿的硬币的总价值最高谁就是王者。问第一个拿硬币的人能否成王。
state： DP[i]表示从i到end能取到的最大value function： 当我们走到i时，有两种选择 取values[i] 取values[i] + values[i+1] 1. 我们取了values[i],对手的选择有 values[i+1]或者values[i+1] + values[i+2] 剩下的最大总value分别为DP[i+2]或DP[i+3], 对手也是理性的所以要让我们得到最小value, 所以 value1 = values[i] + min(DP[i+2], DP[i+3]) 2. 我们取了values[i]和values[i+1] 同理 value2 = values[i] + values[i+1] + min(DP[i+3], DP[i+4]) 最后 DP[I] = max(value1, value2)
public boolean firstWillWin(int[] values) { int n = values.length; if (n <= 2) { return true; } if (n == 3) { return (values[0] + values[1]) > values[2]; } int[] dp = new int[n]; // initialization dp[n - 1] = values[n - 1]; dp[n - 2] = values[n - 2] + values[n - 1]; dp[n - 3] = values[n - 3] + values[n - 2]; dp[n - 4] = values[n - 4] + Math.min(dp[n - 2], dp[n - 1]); dp[n - 4] = Math.max(dp[n - 4], values[n - 4] + values[n - 3]); // dp function for (int i = n - 5; i >= 0; i--) { dp[i] = values[i] + Math.min(dp[i + 2], dp[i + 3]); dp[i] = Math.max(dp[i], values[i] + values[i + 1] + Math.min(dp[i + 3], dp[i + 4])); } int sum = 0; for (int i = 0; i < n; i++) { sum += values[i]; } // result return dp[0] > (sum - dp[0]); }396. Coins in a Line III
还是两个人轮流从拿硬币，也是一次能拿2个或者1个，谁拿的硬币的总价值最高谁就是王者。但是条件改了，两个人不一定要在同一边拿，可以在选择任意边来拿硬币(可以是左边也可以是右边)
state: dp[i][j] 现在还有第i个到第j个硬币，现在先手取得硬币的最高价值 function: pick_left = min(dp[i + 2][j], dp[i + 1][j - 1]) + coin[i]; pick_right = min(dp[i][j - 2], dp[i + 1][j - 1]) + coin[j]; dp[i][j] = max(pick_left, pick_right); intialize: dp[i][i] = coin[i]; dp[i][i + 1] = max(coin[i], coin[i + 1]); answer: dp[0][n - 1]
public boolean firstWillWin(int[] values) { int n = values.length; if (n <= 2) { return true; } int[][] dp = new int[n][n]; boolean[][] visit = new boolean[n][n]; int res = memorySearch(0, n - 1, dp, visit, values); int sum = 0; for (int i = 0; i < values.length; i++) { sum += values[i]; } return res > (sum - res); } public int memorySearch(int l, int r, int[][] dp, boolean[][] visit, int[] coin) { if (l < 0 || l >= coin.length || r < 0 || r >= coin.length) { return 0; } if (visit[l][r]) { return dp[l][r]; } visit[l][r] = true; if (l > r) { dp[l][r] = 0; } else if (l == r) { dp[l][r] = coin[l]; }else { int pick_left = coin[l] + Math.min(memorySearch(l+1, r-1, dp, visit, coin), memorySearch(l+2, r, dp, visit, coin)); int pick_right = coin[r] + Math.min(memorySearch(l+1, r-1, dp, visit, coin), memorySearch(l, r-2, dp, visit, coin)); dp[l][r] = Math.max(pick_left, pick_right); } return dp[l][r]; }
3 双序列动态规划题：
state: f[i][j]代表了第一个sequence的前i个数字／字符，配上第二个sequence的前j个... function: f[i][j] = 研究第i个和第j个的匹配关系 initialize: f[i][0] 和f[0][i] answer: f[n][m] n = s1.length(); m = s2.length()
77. Longest Common Subsequence
LCS经典问题 state：f[i][j] 表示第一个字符串的前i个字符配上第二个字符串的前j个字符的LCS长度 function：注意研究的是第i个字符和第j个字符的关系 a[i - 1] 与 b［j - 1］的关系 if (a[i - 1] == b[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } initialize：f[i][0] = 0; f[0][j] = 0; answer：f[n][m];
public int longestCommonSubsequence(String A, String B) { int n = A.length(); int m = B.length(); // 状态 int[][] f = new int[n + 1][m + 1]; // 初始化 for (int i = 0; i <= n; i++) { f[i][0] = 0; } for (int i = 0; i <= m; i++) { f[0][i] = 0; } // 方程 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); if (A.charAt(i - 1) == B.charAt(j - 1)) { f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1); } } } // 结果 return f[n][m]; } 79. Longest Common Substringf[i][j] 表示第一个字符串的前i个字符配上第二个字符串的前j个字符的LCS长度，是上道题的变种，注意状态转移方程的公式稍微做了变化。
public int longestCommonSubstring(String A, String B) { int n = A.length(); int m = B.length(); // 状态 int[][] f = new int[n + 1][m + 1]; // 初始化 for (int i = 0; i <= n; i++) { f[i][0] = 0; } for (int i = 0; i <= m; i++) { f[0][i] = 0; } // 方程 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (A.charAt(i - 1) == B.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = 0; } } } int max = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (f[i][j] > max) { max = f[i][j]; } } } // 结果 return max; }
581. Longest Repeating Subsequence
是77那道题的变种，geeksforgeeks上有描述：http://www.geeksforgeeks.org/longest-repeating-subsequence/
public int longestRepeatingSubsequence(String str) { int n = str.length(); // state int[][] dp = new int[n + 1][n + 1]; // initialize for (int i = 0; i < n; i++) { dp[i][0] = 0; dp[0][i] = 0; } // dp function for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (str.charAt(i - 1) == str.charAt(j - 1) && i != j) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } // result return dp[n][n]; }
119. Edit Distance
给定单词A和B，其中一个单词可以通过给定的3种操作(插入一个字符，删除一个字符，替换一个字符)变换到另一个单词。完成这样的转换所需要的最少步骤是多少。
state: f[i][j]表示A的前i个字符最少要用几次编辑可以变成B的前j个字符 function: f[i][j] = f[i-1][j-1] // A[i - 1] == B[j - 1] = MIN(f[i-1][j]+1, f[i][j-1]+1, f[i-1][j-1]+1) // A[i - 1] != B[j - 1] initialize: f[i][0] = i, f[0][j] = j answer: f[n][m]
public int minDistance(String A, String B) { int n = A.length(); int m = B.length(); // 状态 int[][] f = new int[n + 1][m + 1]; // 初始化 for (int i = 0; i <= n; i++) { f[i][0] = i; } for (int i = 0; i <= m; i++) { f[0][i] = i; } // 方程 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (A.charAt(i - 1) == B.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1]; } else { f[i][j] = 1 + Math.min(f[i-1][j-1], Math.min(f[i][j-1], f[i-1][j])); } } } // 结果 return f[n][m]; }623. K Edit Distance
给定一个字符串数组和一个目标字符串，对每个字符串可以进行3种类型的操作(插入一个字符，删除一个字符，替换一个字符)使之变成target。然后再给你一个k，代表只能通过k次操作转换，把字符串数组里能通过k此变换变成target的字符串找出来并且输出。比如Given words = ["abc", "abd", "abcd", "adc"] and target = "ac", k = 1 Return ["abc", "adc"]
这道题的思路得结合trie树和动态规划：
class TrieNode { // Initialize your data structure here. public TrieNode[] children; public boolean hasWord; public String str; // Initialize your data structure here. public TrieNode() { children = new TrieNode[26]; for (int i = 0; i < 26; ++i) children[i] = null; hasWord = false; } // Adds a word into the data structure. static public void addWord(TrieNode root, String word) { TrieNode now = root; for(int i = 0; i < word.length(); i++) { Character c = word.charAt(i); if (now.children[c - 'a'] == null) { now.children[c - 'a'] = new TrieNode(); } now = now.children[c - 'a']; } now.str = word; now.hasWord = true; } } public class Solution { /** * @param words a set of stirngs * @param target a target string * @param k an integer * @return output all the strings that meet the requirements */ public List<String> kDistance(String[] words, String target, int k) { // Write your code here TrieNode root = new TrieNode(); for (int i = 0; i < words.length; i++) TrieNode.addWord(root, words[i]); List<String> result = new ArrayList<String>(); int n = target.length(); int[] dp = new int[n + 1]; for (int i = 0; i <= n; ++i) dp[i] = i; find(root, result, k, target, dp); return result; } public void find(TrieNode node, List<String> result, int k, String target, int[] dp) { int n = target.length(); // dp[i] 表示从Trie的root节点走到当前node节点，形成的Prefix // 和 target的前i个字符的最小编辑距离 if (node.hasWord && dp[n] <= k) { result.add(node.str); } int[] next = new int[n + 1]; for (int i = 0; i <= n; ++i) next[i] = 0; for (int i = 0; i < 26; ++i) if (node.children[i] != null) { next[0] = dp[0] + 1; for (int j = 1; j <= n; j++) { if (target.charAt(j - 1) - 'a' == i) { next[j] = Math.min(dp[j - 1], Math.min(next[j - 1] + 1, dp[j] + 1)); } else { next[j] = Math.min(dp[j - 1] + 1, Math.min(next[j - 1] + 1, dp[j] + 1)); } } find(node.children[i], result, k, target, next); } } }4 划分型动态规划
在一个大的区间内找一个小的区间 划分类的题目，基本思路都是用一个local数组和一个gobal数组，然后进行遍历。 之所以可以用变量来代替数组，是因为做了滚动数组的优化.
5 区间类DP
特点： 1. 求一段区间的解max/min/count 2. 转移方程通过区间更新 3. 从大到小的更新
476. Stone Game
有一个石头数组，每个元素代表每个石头的重量。每次可以合并相邻的2个石头，合并后的总重量就这次合并操作的分数。合并一只进行，知道所有石头都合并成了1个石头堆。求最小的合并分数之和。比如[4, 1, 1, 4], in the best solution, the total score is 18:
1. Merge second and third piles => [4, 2, 4], score +2 2. Merge the first two piles => [6, 4]，score +6 3. Merge the last two piles => [10], score +10 如果我们模拟这种操作，很容易会想到brute force的方法。我们得换种思路，从结果往出发点倒推来看。最后得到的元素是10，那么10最后一步可能是从这么几种可能组合变来的：[4,1 | 1,4] 或者 [4, | 1,1,4] 或者 [4,1,1 | 4]，假如我们用dp[i][j]表示从下标i到j能获得的最小的分数。那么dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j}State: dp[i][j] 表示把第i到第j个石子合并到一起的最小花费 Function: 预处理sum[i,j] 表示i到j所有石子价值和 dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j} Intialize: for each i dp[i][i] = 0 Answer: dp[0][n-1]
public int stoneGame(int[] A) { if (A == null || A.length == 0) { return 0; } int m = A.length; // state int[][] sum = new int[m][m]; int[][] dp = new int[m][m]; boolean[][] visit = new boolean[m][m]; // initialize sum array for (int i = 0; i < m; i++) { sum[i][i] = A[i]; dp[i][i] = 0; visit[i][i] = true; for (int j = i + 1; j < m; j++) { sum[i][j] = sum[i][j - 1] + A[j]; } } // dp function for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { dp[i][j] = memoryDP(dp, visit, sum, i, j); } } // result return dp[0][m - 1]; } public int memoryDP(int[][] dp, boolean[][] visit, int[][] sum, int i, int j) { if (visit[i][j]) { return dp[i][j]; } dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int tmp = memoryDP(dp, visit, sum, i, k) + memoryDP(dp, visit, sum, k + 1, j) + sum[i][j]; dp[i][j] = Math.min(tmp, dp[i][j]); } visit[i][j] = true; return dp[i][j]; }
593. Stone Game II
是上道题的变种，变化是数组首尾元素是可以相邻的。For [1, 4, 4, 1], in the best solution, the total score is 18:
1. Merge 1st and 4th piles => [2, 4, 4], score +2 2. Merge the first two piles => [6, 4]，score +6 3. Merge the last two piles => [10], score +10 那么我们就把数组长度翻翻，把所有的再复制一份，放在最后一个石子的后面，这样就可以“连”着了。只不过结果不再是dp[0][m-1]了，结果是{dp[0][m-1], dp[1][m], ... , dp[m-1][2m-2]}的最小值： public int stoneGame2(int[] A) { if (A == null || A.length == 0) { return 0; } int m = A.length; // state int[][] sum = new int[m * 2][m * 2]; int[][] dp = new int[m * 2][m * 2]; boolean[][] visit = new boolean[m * 2][m * 2]; // initialize sum array for (int i = 0; i < m * 2; i++) { sum[i][i] = A[i % m]; dp[i][i] = 0; visit[i][i] = true; for (int j = i + 1; j < m * 2; j++) { sum[i][j] = sum[i][j - 1] + A[j % m]; } } // dp function for (int i = 0; i < m * 2; i++) { for (int j = 0; j < m * 2; j++) { dp[i][j] = memoryDP(dp, visit, sum, i, j); } } // result int ans = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { ans = Math.min(ans, dp[i][i + m - 1]); } return ans; } public int memoryDP(int[][] dp, boolean[][] visit, int[][] sum, int i, int j) { if (visit[i][j]) { return dp[i][j]; } dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int tmp = memoryDP(dp, visit, sum, i, k) + memoryDP(dp, visit, sum, k + 1, j) + sum[i][j]; dp[i][j] = Math.min(tmp, dp[i][j]); } visit[i][j] = true; return dp[i][j]; } 168. Burst Balloons打气球，规则如下：
nums = [4, 1, 5, 10] burst 1, get coins 4 * 1 * 5 = 20 nums = [4, 5, 10] burst 5, get coins 4 * 5 * 10 = 200 nums = [4, 10] burst 4, get coins 1 * 4 * 10 = 40 nums = [10] burst 10, get coins 1 * 10 * 1 = 10 Total coins 20 + 200 + 40 + 10 = 270 同样的这道题我们要用逆向思维处理，从结果往开始倒推。State: dp[i][j] 表示把第i到第j个气球打爆的最大价值 Function: 对于所有k属于{i,j}, 表示第k号气球最后打爆。 midValue = arr[i- 1] * arr[k] * arr[j+ 1]; dp[i][j] = max(dp[i][k-1]+dp[k+1][j]+midvalue) Intialize: for each i dp[i][i] = 0 Answer: dp[0][n-1]
枚举最后一个打破的气球是哪个。深刻理解，从最后剩下一个气球还是递归，分别求左右两边。对于边界情况的处理，新开了一个数组，两边分别放了一个1
public int maxCoins(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length + 2; // state int[][] dp = new int[n][n]; boolean[][] visit = new boolean[n][n]; int[] arr = new int[n]; // initialize arr[0] = arr[n - 1] = 1; for (int i = 1; i < n - 1; i++) { arr[i] = nums[i - 1]; } // dp function for (int i = 1; i < n - 1; i++) { for (int j = 1; j < n - 1; j++) { dp[i][j] = memorySearch(dp, visit, arr, i, j); } } return dp[1][n - 2]; } public int memorySearch(int[][] dp, boolean[][] visit, int[] arr, int i, int j) { if (visit[i][j]) { return dp[i][j]; } int res = 1; for (int k = i; k <= j; k++) { int left = memorySearch(dp, visit, arr, i, k - 1); int right = memorySearch(dp, visit, arr, k + 1, j); int mid = arr[k] * arr[i - 1] * arr[j + 1]; dp[i][j] = Math.max(dp[i][j], mid + left + right); } visit[i][j] = true; return dp[i][j]; }430. Scramble String
我们提出维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。 有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]。判断这个是不是满足，其实我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的，因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。 上面说的是劈一刀的情况，对于s1[i...i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立，那么两个串就是scramble的。 总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k 如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是相当有用的，空间复杂度是O(n^3)。注意处理for循环的边界条件，代码如下：
public boolean isScramble(String s1, String s2) { if (s1 == null || s2 == null || s1.length() != s2.length()) { return false; } int n = s1.length(); // state boolean[][][] dp = new boolean[n][n][n + 1]; // initialize for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j][1] = s1.charAt(i) == s2.charAt(j); } } // dp function for (int len = 2; len <= n; len++) { for (int i = 0; i < n && i + len <= n; i++) { for (int j = 0; j < n && j + len <= n; j++) { for (int k = 1; k < len; k++) { dp[i][j][len] = dp[i][j][len] || dp[i][j][k] && dp[i+k][j+k][len-k] || dp[i][j+len-k][k] && dp[i+k][j][len-k]; } } } } // result return dp[0][0][n]; }6 记忆化搜索题：
我们常见的动态规划问题，比如流水线调度问题，矩阵链乘问题等等都是“一步接着一步解决的”，即规模为 i 的问题需要基于规模 i-1 的问题进行最优解选择，通常的递归模式为DP(i)=optimal{DP(i-1)}。而记忆化搜索本质上也是DP思想，当子问题A和子问题B存在子子问题C时，如果子子问题C的最优解已经被求出，那么子问题A或者是B只需要“查表”获得C的解，而不需要再算一遍C。记忆化搜索的DP模式比普通模式要“随意一些”，通常为DP(i)=optimal(DP(j)), j < i。
397. Longest Increasing Continuous Subsequence
在一个数组中找到最长递增子序列的长度，子序列必须是连续的。方法就是从左往右扫一遍，从右往左也扫一遍。然后扫描的时候更新最大值就好。
public int longestIncreasingContinuousSubsequence(int[] A) { if (A == null || A.length == 0) { return 0; } int n = A.length; int ans = 1; int length = 1; for (int i = 1; i < n; i++) { if (A[i] > A[i-1]) { length++; } else { length = 1; } ans = Math.max(ans, length); } length = 1; for (int i = n - 2; i >= 0; i--) { if (A[i] > A[i+1]) { length++; } else { length = 1; } ans = Math.max(ans, length); } return ans; }
398. Longest Increasing Continuous subsequence II
在一个矩阵里找到最长递增的子序列有多长。比如给定如下矩阵的话，就返回25：
[ [1 ,2 ,3 ,4 ,5], [16,17,24,23,6], [15,18,25,22,7], [14,19,20,21,8], [13,12,11,10,9] ]这道题可以用记忆化搜索来解决。
state：
dp[x][y] 以x,y作为结尾的最长子序列 function: 遍历x，y上下左右4个格子 dp[x][y] = dp[nx][ny] + 1 (if a[x][y] > a[nx][ny]); intialize: dp[x][y]是极小值时，初始化为1 //表示以xy作为结尾的最长子序列至少是有1个！ answer: dp[x][y]中的最大值 这种做法保证了以每个点作为最长子序列的结尾的情况，只会遍历一次。对于已经遍历过的点dp[x][y] 一定是最优解！ 这道题的另外一个马甲是滑雪题，在二维数组上，只能从大的数往小的数滑，问最长滑多远。
public int longestIncreasingContinuousSubsequenceII(int[][] A) { if (A.length == 0) { return 0; } int n = A.length; int m = A[0].length; int ans = 0; int[][] dp = new int[n][m]; int[][] flag = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = search(i, j, A, dp, flag); ans = Math.max(ans, dp[i][j]); } } return ans; } public int search(int x, int y, int[][] A, int[][] dp, int[][] flag) { if (flag[x][y] != 0) { return dp[x][y]; } int []dx = {1, -1, 0, 0}; int []dy = {0, 0, 1, -1}; int ans = 1; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; int n = A.length; int m = A[0].length; if (0 <= nx && nx < n && 0 <= ny && ny < m) { if (A[x][y] > A[nx][ny]) { ans = Math.max(ans, search(nx, ny, A, dp, flag) + 1); } } } flag[x][y] = 1; dp[x][y] = ans; return ans; } 200. Longest Palindromic Substring在一个字符串中找到最长的回文子串，这道题可能有2种变型，一种是让你求这个最长回文子串的长度，另外一种是求出这个子串是啥。这道题是要求求出子串的string。
可以用“中出法”解决这道题，从每个点i往两边扩散，如果arr[i-1] == arr[i+1]，那么回文子串的长度就扩大了，一直扩散直到不能扩散为止。对每个点都进行这样的操作，中途用变量记录更新最大值就好。然后记得注意处理字符串长度为偶数的情况，时间复杂度是O(n*n)，空间复杂度O(1):
public String longestPalindrome(String s) { return middleOut(s); } public String middleOut(String s) { if (s == null || s.length() <= 0) { return null; } String res = ""; for (int i = 0; i < s.length(); i++) { String tmp = searchPalindrome(s, i, i); res = tmp.length() > res.length() ? tmp : res; if (i - 1 >= 0 && s.charAt(i-1) == s.charAt(i)) { tmp = searchPalindrome(s, i - 1, i); res = tmp.length() > res.length() ? tmp : res; } } return res; } public String searchPalindrome(String s, int l, int r) { while (l >= 0 && r < s.length()) { int nextL = l - 1, nextR = r + 1; if (nextL >= 0 && nextR < s.length() && s.charAt(nextL) == s.charAt(nextR)) { l--; r++; } else { break; } } return s.substring(l, r + 1); }DP的方法请参见博文： http://www.cnblogs.com/grandyang/p/4464476.htmlLeetCode上有一道很类似的题目，只不过是子序列而不是子串了
LeetCode 516. Longest Palindromic Subsequence
这道题给了我们一个字符串，让我们求最大的回文子序列，子序列和子字符串不同，不需要连续。而关于回文串的题之前也做了不少，处理方法上就是老老实实的两两比较吧。像这种有关极值的问题，最应该优先考虑的就是贪婪算法和动态规划，这道题显然使用DP更加合适。我们建立一个二维的DP数组，其中dp[i][j]表示[i,j]区间内的字符串的最长回文子序列，那么对于递推公式我们分析一下，如果s[i]==s[j]，那么i和j就可以增加2个回文串的长度，我们知道中间dp[i + 1][j - 1]的值，那么其加上2就是dp[i][j]的值。如果s[i] != s[j]，那么我们可以去掉i或j其中的一个字符，然后比较两种情况下所剩的字符串谁dp值大，就赋给dp[i][j]，那么递推公式如下： / dp[i + 1][j - 1] + 2 if (s[i] == s[j]) dp[i][j] = \ max(dp[i + 1][j], dp[i][j - 1]) if (s[i] != s[j])
我们也可以用记忆化搜索的方式来求得dp方程的值，时空复杂度都是O(n*n)：
public int longestPalindromeSubseq(String s) { return dpMethod(s); } public int dpMethod(String s) { int n = s.length(); // state int[][] dp = new int[n][n]; boolean[][] visit = new boolean[n][n]; // initialize for (int i = 0; i < n; i++) { dp[i][i] = 1; visit[i][i] = true; } // memorized search for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { memorySearch(s, dp, visit, i, j); } } // result return dp[0][n - 1]; } public int memorySearch(String s, int[][] dp, boolean[][] visit, int i, int j) { if (i < 0 || i > s.length() || j < 0 || j > s.length()) { return 0; } if (visit[i][j]) { return dp[i][j]; } if (i > j) { dp[i][j] = 0; return 0; } if (s.charAt(i) == s.charAt(j)) { dp[i][j] = memorySearch(s, dp, visit, i+1, j-1) + 2; } else { dp[i][j] = Math.max(memorySearch(s, dp, visit, i, j-1), memorySearch(s, dp, visit, i+1, j)); } visit[i][j] = true; return dp[i][j]; }
我们先通过一道题目来认识一下DP：
109. Triangle
有一个数字三角形，从上往下走，找到一条最短的从根到叶节点的路径，即各个节点上的数字加起来的和最小。比如：
[ [2], [3,4], [6,5,7], [4,1,8,3] ] 那么最小的路径和就是2 + 3 + 5 + 1 = 11。这道题有点类似于求二叉树的最小路径和，但是和二叉树有区别，因为二叉树每个节点只有2个子节点。递归的时候，子递归不会进入兄弟节点的后代。
如果这道题直接套用二叉树的那种递归思想，那我们会写出如下的DFS的代码：
但是这个代码超时了，时间复杂度是O(2^n)。
接下来再用divide & conquer分治法来看这道题:
然并卵，这个解法和DFS的时间复杂度一样，一样会TLE超时
以上方法超时的原因，就在于有些点被访问了不止一次，而是多次，所以我们要加入Hash表，来进行记忆化搜索。代码如下：
这样的代码就是可以AC的。一共有O(n*n)个节点，每个节点只被访问一次，所以总的时间复杂度是O(n*n)。这就是加了记忆化搜索的分治法。
而DP和分治法的区别就在于DP有脑子，去掉了重复的运算。动态规划快，就在于它去掉了重复运算。
