常见动态规划

动态规划，最重要：找到状态转移公式。

从前一个状态到后一个状态，一般有一个新的数组存放状态

努力思考，从简单的状态想到复杂的状态

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

 示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

仔细思考，长为1，2,3的情况十分清晰明了。

class Solution {
public:

    int rob(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        vector<int> tmp(nums.size(),0);
        tmp[0]=nums[0];
        if(nums.size()>1)
            tmp[1]=max(nums[0],nums[1]);
        if(nums.size()>2){
            tmp[2]=max(nums[1],nums[0]+nums[2]);
        }

        for(int i=3;i<nums.size();i++){
            tmp[i] = max(nums[i]+tmp[i-2],tmp[i-1]);
        }
        return tmp[nums.size()-1];
    }
};

最长递增子序列

值得注意的是，这个题不是一次遍历可以解决的。

dp[j] = max(dp[i]) +1 i是所有的比j小的数(但是多次遍历并不麻烦)

300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int> tmp(nums.size(),1);
        // tmp[0]=1;
        
        //值得注意的是，这个题不是一次遍历可以解决的。
        // dp[j] = max(dp[i]) +1 i是所有的比j小的数。
        for(int i=1;i<nums.size();i++){
            int now = 0;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    now = max(now,tmp[j]);
                }
            }
            tmp[i] = now+1;

        }
        sort(tmp.begin(),tmp.end());
        return tmp[tmp.size()-1];
    }
};

时间复杂度：O(n^2)，其中 n为数组nums 的长度。动态规划的状态数为 n，计算状态 dp[i]时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2)

空间复杂度：O(n)，需要额外使用长度为 n 的 dp 数组。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心+二分查找，可以有O(nlogn)的时间复杂度。

最大连续子序列和

很简单的一道题，前一个状态到下一个状态。

状态方程：dp[i] = max(dp[i-1]+A[i],A[i])

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

 

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

主要是厘清思路。

1）

                if(text1[i]==text2[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }

2）注意开头需要补充

        for(int j=1;j<text1.length();j++){
            if(text1[j]==text2[0]){
                dp[j][0]=1;            
            }else{
                dp[j][0]=dp[j-1][0];
            }
        }

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if(text1.length()==0 ||text2.length()==0){
            return 0;
        }
        vector< vector<int> > dp(text1.length(),vector<int>(text2.length(),0));
        if(text1[0]==text2[0]){
            dp[0][0]=1;
        }else{
            dp[0][0]=0;
        }
        for(int i=1;i<text2.length();i++){         
            if(text1[0]==text2[i]){//这里也要有比较,开始忘记了。
                dp[0][i]=1;
            }else{
                 dp[0][i]=dp[0][i-1];
            }
        }
        for(int j=1;j<text1.length();j++){
            if(text1[j]==text2[0]){
                dp[j][0]=1;            
            }else{
                dp[j][0]=dp[j-1][0];
            }
        }
        for(int i=1;i<text1.length();i++){
            for(int j=1;j<text2.length();j++){
                if(text1[i]==text2[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[text1.length()-1][text2.length()-1];

    }
};

最长回文子串

注意：

最长回文子串不是一个求长度问题，而是一个是否问题。

思路，

1.长度为1的回文串，填矩阵。

2.长度为2的回文串有没有，填矩阵。

3.长度为3~n的回文串有没有。所以最外层循环是从3~n。i,i+j-1如果相等，看i+1,i+j-2是不是回文字符串。

是否是回文子串：

                    if(s[j]==s[q]){
                        dp[j][q]=dp[j+1][q-1];
                        if(dp[j][q]>0){
                            maxn=i;
                            start=j;
                        }
                    }else{
                        dp[j][q]=0;//不是回文子串
                    }

class Solution {
public:
    string longestPalindrome(string s) {
        //先填对角线。
        //再看长度为2
        if(s.length()==0)
        return "";
        if(s.length()==1){
            return s;
        }
        int maxn=1;
        int start=0;
        //true false问题
        vector< vector<int> > dp(s.length(),vector<int>(s.length(),0));
        for(int i=0;i<s.length();i++){
            dp[i][i]=1;
        }
        for(int i=0;i<s.length()-1;i++){
            if(s[i]==s[i+1]){
                dp[i][i+1]=1;
                maxn=2;
                start=i;
            }else{
                dp[i][i+1]=0;
            }
        }
        for(int i=3;i<=s.length();i++){
            for(int j=0;j<s.length();j++){
                int q=j+i-1;//q代表长度，j代表坐标
                
                if(q<s.length()){
                    if(s[j]==s[q]){
                        dp[j][q]=dp[j+1][q-1];
                        if(dp[j][q]>0){
                            maxn=i;
                            start=j;
                        }
                    }else{
                        dp[j][q]=0;//不是回文子串
                    }
                    // cout<<j<<"\t"<<q<<"\t"<<dp[j][q]<<endl;
                }
                
            }
        }
        // cout<<dp[0][s.length()-1]<<endl;
        return s.substr(start,maxn);


    }
};