动态规划

动态规划的实质其实就是穷举，通过DP表的形式折叠一些重复的计算。dp其实没有什么好的模板，重点在于写出状态转移方程。但是即使写出了状态转移方程还是有很多细节需要注意。 总的来说DP的模板可以归结成如下：

//初始化 dp[0][0] = base; //进行状态转移 for(状态1 in 状态1所有的取值) for(状态2 in 状态2所有的取值) dp[状态1][状态2] = 状态转移方程

不过这也太笼统了吧，还是来看几道经典的DP吧。

最长回文子串

题目：https://leetcode-cn.com/problems/longest-palindromic-substring/ 题目大意：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

分析：这道题是DP的经典问题了。 其实判断回文子串就是一个自己和自己比较的过程，我们初始化一个二维数组，比较每个位置的上的字符是否相等，如果相等的话那么向中间继续比较。 写成状态转移方程就是 dp[i][j] = A[i] == A[j]? dp[i-1][j+1]:false

当然对于一些特殊情况还是需要进行考虑，对于回文子串来说一共有两种情况。第一种就是奇数长度，在这种情况下经过不断DP，最后会查找到i = j的位置上，所以我们需要把i = j位置的上的boolean初始化为true。 第二种就是偶数长度，这种情况下最后会归结到一个空的字符串上，对于这种情况，我们可以像以往一样采用dp[i][j]代表A[i-1]和A[j-1]的字符串进行比较，也可以直接进行判断，如果j-i<3&&A[i] == A[j]那么dp[i][j] = true。

class Solution { public String longestPalindrome(String s) { if(s == null || s.length() == 0) return s; char[] chars = s.toCharArray(); boolean[][] dp = new boolean[s.length()][s.length()]; //如果不设置成1的话 //会导致如果字符串没有回文子串会返回"" //但是实际上应该返回第一个字符 //因为一个字符就是一个回文串 int maxLen = 1; //保存最长回文子串的起始位置 int begin = 0; for(int i=0;i<s.length();i++) dp[i][i] = true; for(int i=1;i<s.length();i++){ //由于数组是对称的，所以计算一半就行 for(int j=0;j<i;j++){ if(chars[i] == chars[j]){ if(i-j<3){ dp[i][j] = true; }else{ //向中间比较 dp[i][j] = dp[i-1][j+1]; } }else{ dp[i][j] = false; } //是回文子串才能记录最大值 if(dp[i][j] && i-j+1>maxLen){ maxLen = i-j+1; begin = j; } } } return s.substring(begin,begin+maxLen); } }

编辑距离

题目：https://leetcode-cn.com/problems/edit-distance/ 题目大意：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。 分析：这道题看起来非常复杂，但是看了解答之后会有一种恍然大悟的感觉。 对于一个字符rose有三种操作，如果要转化为ros采用删除操作，操作数+1. 那么对于rorse转化为rose也是采用删除操作，操作数+1,。 通过这么倒推之后我们发现，前面的操作依赖于后面的操作，那么对于这种题目就可以采用动态规划来做。 我们创建一个数组int[][] dp，对于dp[i][j]代表的是字符串word1[:i-1]和word2[:j-1]。 如果word1[i-1] == word2[j-2],那么这一步不需要进行任何操作。 如果不相等，那么一共有三种操作。 例如，对于目标字符串a，假设目前字符串为ab，那么采用删除操作，然后比较的 是a和a，所以就是比较w[i-1]和w[j]也就是dp[i-1][j]。 假设目标字符串为ab，目标字符串为abc，那么采用添加操作，然后就是比较ab和ab，所以就是比较w1[i]和w[j-1]也就是dp[i][j-1]。 假设目标字符串为abc，当前字符串为abd，那么采用替换操作，也就是比较w[i-1]和w[j-1]，也就是dp[i-1][j-1]。 所以得出结论，替换依赖于dp[i-1][j-1]，添加依赖于dp[i][j-1]，删除依赖于dp[i-1][j]。 由于需要求的是最小距离，所以我们需要在这三个数中取最小值，所以状态转移方程为 dp[i][j] = w1[i]==w2[j]?dp[i-1][j-1]:Min(dp[i-1][j],dp[i][j-1],dp[i-1]][j-1])+1

class Solution { public int minDistance(String word1, String word2) { if(word1 == null && word2 == null) return 0; if(word1.length() == 0 && word2.length() == 0) return 0; if(word1 == null) return word2.length(); if(word2 == null) return word1.length(); char[] chars1 = word1.toCharArray(); char[] chars2 = word2.toCharArray(); int[][] dp = new int[word1.length()+1][word2.length()+1]; for(int i=0;i<word1.length()+1;i++){ dp[i][0] = i; } for(int i=0;i<word2.length()+1;i++){ dp[0][i] = i; } for(int i=1;i<word1.length()+1;i++){ for(int j=1;j<word2.length()+1;j++){ if(chars1[i-1] == chars2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ //记得操作+1 dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; } } } return dp[word1.length()][word2.length()]; } }

最长重复子数组

题目：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/ 题目大意：给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 分析：这道题其实就是经典的最长公共子串的变形。 dp[i][j] = nums[i] == nums[j]?dp[i-1][j-1]+1:0

class Solution { public int findLength(int[] A, int[] B) { if(A == null || B == null) return 0; int max = 0; int[][] dp = new int[A.length+1][B.length+1]; for(int i=1;i<A.length+1;i++){ for(int j=1;j<B.length+1;j++){ if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = 0; if(dp[i][j] != 0) max = Math.max(max,dp[i][j]); } } return max; } }

最长公共子序列

题目：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/submissions/ 题目大意：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。

分析：其实这道题和上面那道差不多，但是区别在于这道题的序列是可以不连续的，但是顺序要相同。 那么对于字符abcde和ace来说。 假设我们以abcde为主，逐个比较text2ace，当text2为a的时候此时公共子序列为1，为ac的时候，子序列为1，为ace的时候子序列为2。 对于ace也是一样，所以可以得出状态转移方程： dp[i][j] = text1[i-1] == text[j-1]?dp[i-1][j-1]+1:Max(dp[i-1][j],dp[i][j-1])

class Solution { public int longestCommonSubsequence(String text1, String text2) { if(text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0; int[][] dp = new int[text1.length()+1][text2.length()+1]; int lengt1 = text1.length(),length2 = text2.length(); for(int i=1;i<lengt1+1;i++){ for(int j=1;j<length2+1;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[lengt1][length2]; } }

零钱兑换

题目：https://leetcode-cn.com/problems/coin-change/ 题目大意：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

分析：这道题其实算是完全背包问题，比起上面的题目代码上稍微简单一些。 状态转移方程是: dp[i] = i>coin?Min(dp[i-coin]+1,dp[i]):dp[i] coin:coins

class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; Arrays.fill(dp,amount+1); dp[0]=0; for(int i=1;i<amount+1;i++){ for(int coin:coins){ if(i-coin>=0 && dp[i-coin]!=amount+1){ dp[i] = Math.min(dp[i],dp[i-coin]+1); } } } return dp[amount] == amount+1?-1:dp[amount]; } }