[数据结构与算法]剑指Offer动态规划题解

剑指Offer动态规划题解（持续更新中-2021-08-24）

JZ30 连续子数组的最大和

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n=array.length;
        if(n==0) return 0;
        int [] dp=new int[n];
        //初始化dp
        for(int i=0;i<n;i++){
            dp[i]=Integer.MIN_VALUE;//初始化状态
        }
        //DP[i] 表示的是以 i 为结束位置的最大子数组之和。
        dp[0]=array[0];
        
        int res=dp[0];//要返回的结果
        
        for(int i=1;i<n;i++){
            dp[i]=Math.max(array[i],dp[i-1]+array[i]);// 如果dp[i-1]贡献是负的，就不要了
            res=Math.max(dp[i],res);//拿现在的结果和之前的最大值比较
        }
        return res;//返回全局最大值
    }
}

空间复杂度优化

DP[i]仅和DP[i-1]的状态有关，因此可以进行状态压缩，即降低备忘录的空间复杂度。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int n=array.length;
        if(n==0) return 0;
        int [] dp=new int[n];
        int dp_0=array[0];//表示前一个状态
        int dp_1 ;//表示现在的状态
        int res=dp_0;//要返回的结果
        
        for(int i=1;i<n;i++){
            dp_1=Math.max(array[i],dp_0+array[i]);// 如果dp_0贡献是负的，就不要了。
            dp_0=dp_1;
            res=Math.max(dp_1,res);
        }
        return res;
    }
}

leetcode 5 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

#分析
#状态转移矩阵，用到了上三角
# 对角线均为 true

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2) return s;//长度小于2默认为回文子串

        int begin=0; //最长回文子串的初始位置
        int maxLen=1;//最长回文子串长度
        char [] arr=s.toCharArray();

        boolean[][] dp=new boolean[len][len]; //状态转移矩阵
        for(int i=0;i<len;i++){
            dp[i][i]=true;//对角线上长度为1的子串，为true；
        }
		//递推开始
        //枚举字符串长度L
        for(int L=2;L<=len;L++){
            //枚举左边界
            for(int i=0;i<len;i++){//上三角
                //根据左边界以及字符串长度可以确定 有边界j
                int j=L+i-1;
                //如果右边界越界，就可以退出当前循环
                if(j>=len){
                    break;
                }
                if(arr[i]!=arr[j]){
                    dp[i][j]=false;
                }else{
                    if(j-i<3){
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];//依赖于上一个状态
                    }
                }
                 // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if(dp[i][j]==true&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    begin=i;
                }
            }           
        }
        return s.substring(begin,begin+maxLen);
    }
}