动态规划

例一：

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。

代码：

class Solution { public: int findLength(vector<int>& A, vector<int>& B) { int num=0; int x=A.size(); int y =B.size(); vector<vector<int>> dp(x+1,vector<int>(y+1,0)); for(int i=1;i<=x;i++) { for(int j =1;j<=y;j++) { dp[i][j]=A[i-1]==B[j-1]?dp[i-1][j-1]+1:0; num=max(num,dp[i][j]); } } return num; } };

图解：

递推公式为：

if(A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=0;

奔向题源Leetcode

例二：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

代码：

class Solution { public: int maxSubArray(vector<int>& nums) { int my=nums[0]; int l =nums.size(); vector<int> dp(l,0); dp[0]=nums[0]; for(int i=1;i<l;i++) { dp[i]=dp[i-1]>0?nums[i]+dp[i-1]:nums[i]; my=max(my,dp[i]); } return my; } };

图解：

初始状态：dp[0]=nums[0]，即以 nums[0] 结尾的连续子数组最大和为nums[0] 。

返回值： 返回 dp 列表中的最大值，代表全局最大值

奔向题源Leetcode

详情动画连接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

例三：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb"

思路：

1.回文子串的特点2.表达出动态规划的状态转移方程 3.动态规划的边界条件 4.找到最长回文子串的长度和起始坐标

代码：

class Solution { public: string longestPalindrome(string s) { int n = s.size(); //字符的长度 vector<vector<int>> dp(n, vector<int>(n)); //定义储存状态的二维数组dp[i][j];i为字符左端坐标，j为字符右端坐标 if(n<2) return s; //当字符长度小于2的时候，返回其本身，因为n=0为空，n=1为一个字符为回文字符 int begin=0; // 回文开始位置 int sl=1; //回文长度 for(int i=0;i<n;i++) { dp[i][i]=1; //当为长度为1时，即测试自身的时候是回文，记状态为1 } for(int j=1;j<n;j++) //j为字符右端坐标 { for(int i=0;i<j;i++) //i为字符左端坐标 { if(s[i]==s[j]) //当两端字符相同时 { if(j-i<3) dp[i][j]=1; //当字符长度小于3时，此时字符段就是回文，记状态为1 else dp[i][j]=dp[i+1][j-1]; //当字符长度大于等于3时，此时要看内一层的字符段是否是回文了 } else dp[i][j]=0; //当两端字符不相同时，即字符段不是回文，记状态为0 if(dp[i][j]&&j-i+1>=sl) //当字符段是回文，同时字符长度大于1是，更新回文的开始坐标和回文段最大长度 { begin=i; sl=j-i+1; } } } return s.substr(begin,sl); //从源字符串中截取开始位置为begin，长度为sl的字符段 } };

总结： 1.找到动态规划的状态转移方程 2.找到动态规划的边界条件