动态规划最经典的几个问题
最近刷的题有点多，一直没来得及总结，是时候总结了，加油！还有三天。
Maximum SubArray(leetcode 53)
dp[nums.length]，dp[i]表示以nums[i]结尾的最大连续子序列和
边界初始条件dp[0]是nums[0]
状态转移方程:dp[i] = max(dp[i-1] + nums[i], nums[i])
代码：
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];//dp[i]是以下标i元素结尾的最大和
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
if(max < dp[i]){
max = dp[i];
}
}
return max;
}
也可以有一个跟优秀的解法，用一个sum来保存前面得到的子串的数值，当遍历到nums[i]且sum<0的时候，前面的子串对当前的加和是没有贡献的，所以舍弃掉这样的子串，让sum = nums[i]，重新开始子串的累积，而如果sum>0，那么前面的子串对加和是有贡献的，所以继续追加子串，sum = nums[i] + sum；这样每次循环还检验更新最大值就可以了。空间复杂度O(1)
public int maxSubArray(int[] nums){
int sum = nums[0];
int max = sum;
for(int i = 1; i < nums.length; i++){
if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];
}
if(sum > max){
max = sum;
}
}
return max;
}
下面思考一个问题，我们已经求出来maxSum，但是起始和终止位置在什么地方？目前想到的方法，就是用一个list，在每次dp的时候，去检查，详见注释。
//如果要求返回起止位置
public int[] maxSubArray(int[] nums) {
int[] dp = new int[nums.length];//dp[i]是以下标i元素结尾的最大和
dp[0] = nums[0];
int max = dp[0];
List<Integer> record = new ArrayList<>();
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
if(dp[i] == nums[i]){//新序列开始了
record.clear();
record.add(i);
}else{//如果是旧的序列追加
record.add(i);
}
if(max < dp[i]){
max = dp[i];
}
}
int[] result = new int[]{record.get(0),record.get(record.size()-1),max};
return result;
}
Longest Increasing Sequence（leetcode 300）
dp[nums.length[,dp[i]表示以nums[i]结尾的LIS
边界初始条件是所有的dp[i]全部是1（至少有自己一个）
状态转移方程：dp[i] = max(dp[j] + 1，1) 其中j满足nums[j] < nums[i]，且j<i
public int lengthOfLIS(int[] nums) {
if(nums == null||nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
for(int i = 0; i < dp.length; i++){
dp[i] = 1;
}
int max = 1;
for(int i = 1; i < dp.length; i++){
for(int j = 0; j < i; j++){
if(nums[i]>nums[j] && dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
}
}
max = max>dp[i] ? max:dp[i];
}
return max;
}
再思考一个问题，如何获取到LIS序列中有哪些元素？思路是把刚刚dp的过程逆过来，max的那个dp[m]，一定是由值为dp[m]-1并且满足nums[k] < nums[m]的dp[k]来的，同理dp[k]，一定是从值为dp[k]-1并且满足nums[j] < nums[k]的dp[j]来的，以此类推，一直找到dp是1的位置即可。
但问题是，这样的序列可能不止一个....所以有些纠结。。这个问题后面解决。
Longest Common Sequence
输入String a和String b或者是char[] a 和char [] b
dp[aLen+1][bLen+1]二维的数组，dp[i][j]表示的是a的i位置之前和b的j位置之前的LCS（包括i和j）
边界初始条件是dp[i][0]全部是0，dp[0][j]全部是0。
状态转移方程：
从末尾往头看，如果相等那就两个同时往前缩，如果不相等，就去缩其中一个，取最大值。
图示：
代码：
public int findLength(char[] A, char[] B) {
if(A== null || B== null || A.length == 0 || B.length == 0 ){
return 0;
}
int[][] dp = new int[A.length+1][B.length+1];
for(int i = 0; i <= B.length; i++){
dp[0][i] = 0;
}
for(int i = 0; i <= A.length; i++){
dp[i][0] = 0;
}
for(int i = 1; i <= A.length; i++){
for(int j = 1; j <= B.length; j++){
if(A[i-1] == B[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[A.length][B.length];
}
Edit Distance（leetcode 72）
字符串最短编辑距离。输入两个字符串String a, String b
dp[aLen + 1][bLen + 1]，dp[i][j]表示字符串a的i位置之前的子串和b的j位置之前的子串的最短编辑距离。
边界初始条件dp[i][0] 是i，dp[0][j]是j，这是显而易见的，因为一个空串和一个长度为l的字符串的编辑距离，就是l。
状态转移方程还是从末尾看起，根据末尾a[i]和b[j]是不是相等，转移情况分为：
- 如果a[i] == b[j]（注意我们代码中的dp定义的下标都是比字符串的下标前进一个，上面那个题目也是这样的，这里只是为了说明方便一些，让字符串的下标从1开始了），那么这一位就是不需要编辑的。dp[i][j] = dp[i - 1][j - 1]；
- 如果a[i] != b[j]，这个情况就比较复杂了，这涉及到我们怎么去操作。
a.修改操作，如果把a[i]改成b[j]，或者b[j]改成a[i]，那么就操作数加一，两个同时往前缩，我们去关注前面的子串，这样dp[i][j] = dp[i - 1][j - 1] + 1
b.删除操作，把a[i]直接删除掉，去看a的前面的子串有没有可能跟b相等，那么操作数加一，这时候关注的a的指针要前移一位，而对b则还是关注原来的位置，这样dp[i][j] = dp[i - 1][j] + 1，而同理可以去删除b[i]，对应的状态转移方程为dp[i][j] = dp[i][j - 1] + 1
c.添加操作，在a[i]后面去追加个b[i]，这样相当于把a的关注的指针后移到了i+1处，那么接下来要往前缩了，a往前缩就是i，b往前缩就是i-1，所以dp[i][j] = dp[i][j - 1]，而同理，去给b加a[i]的话，结果就是dp[i][j] = dp[i - 1][j]
然后上面的abc中总共下来其实就是3个状态转移方程，取其中的最小值即可。
可以写出下面的代码
public int minDistance(String word1, String word2) {
int aLen = word1.length();
int bLen = word2.length();
int[][] dp = new int[aLen + 1][bLen + 1];
for(int i = 0; i < aLen + 1; i++){
dp[i][0] = i;
}
for(int i = 0; i < bLen + 1; i++ ){
dp[0][i] = i;
}
for(int i = 1; i < aLen + 1; i++){
for(int j = 1; j < bLen + 1; 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[aLen][bLen];
}
Longest Palindromic Substring
输入字符串s
dp[s.size()][s.size()],dp[i][j]表示s[i]到s[j]是否为回文串，dp[i][j]为1表示是，dp[i][j]为0表示不是。
根据s[i]和s[j]是否相等，转移情况如下：
- s[i] == s[j]，这样的话如果s[i + 1] 到 s[j - 1]是回文串，那么i到j就是回文串，如果s[i + 1]到s[j - 1]不是回文串，那么i到j就不是回文串。dp[i][j] = dp[i + 1][j - 1]
- s[i] != s[j]，这样的话s[i]到s[j]一定不是回文串。dp[i][j] = 0
边界初始条件显然是dp[i][i] = 1,自己到自己肯定是个回文，而dp[i][i + 1] = (S[i] == S[i + 1]) ? 1 : 0也是显然的。通过边界条件确定了长度为1和2的回文。这里会遇到一个问题我们枚举i和j的时候，如果按照常规的从小到大的顺序（外层写个i递增，里层嵌套一个j从i递增到尾部，去枚举所有的dp[i][j]），就有可能导致状态无法转移，也就是说dp[i][j]依赖的dp[i+1][j-1]可能还没有计算。这个具体实例参考算法笔记。我们这里要换个思路去枚举i,j，保证每次都能正常的状态转移，我们考虑按照子串的长度和子串的初始位置进行枚举，第一遍将长度为3的子串dp全部求出来，第二遍求4的......代码如下：
我们先来求一下最长的长度
public int longestPalindrome(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i = 0; i < len; i++){
dp[i][i] = 1;
if(i + 1 < len && s.charAt(i) == s.charAt(i+1)){
dp[i][i+1] = ;
}
}
int ans = 1;
for(int L = 3; L < len; L++){
for(int i = 0; i + L - 1< len; i++){
int j = i + L - 1;
if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == 1){
dp[i][j] = 1;
ans = L;
}
}
}
return ans;
}
同样的，我们思考一个问题，能否把这个子串打印出来？
当然，只要在更新的时候记录位置即可。
public String longestPalindrome(String s) {
if(s == null || s.length() == 0){
return "";
}
int len = s.length();
int[][] dp = new int[len][len];
int begin = 0;
int ans = 1;
for(int i = 0; i < len; i++){
dp[i][i] = 1;
if(i + 1 < len && s.charAt(i) == s.charAt(i+1)){
dp[i][i+1] = 1;
ans = 2;
begin = i;
}
}
for(int L = 3; L <= len; L++){
for(int i = 0; i + L - 1< len; i++){
int j = i + L - 1;
if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == 1){
dp[i][j] = 1;
ans = L;
begin = i;
}
}
}
return s.substring(begin, ans + begin);
}
