动态规划
🙈动态规划🙈
转自：🔥【github】
==========
矩阵 (10%)
序列(40%)
双序列(40%)
爬楼梯
Leetcode 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解题思路
- 到达第n阶台阶有两种方式，一个是在第
n-1个台阶处+1阶或在n-2个台阶处+2阶 - 建立一个dp数组，记录到达每一层时的所有方法总数
- 所以到达第n个台阶的方法与到底第
n-1和n-2个台阶相关，dp[n]=dp[n-1]+dp[n-2]1
2
3
4
5
6
7
8
9int climbStairs(int n) {
vector<int> dp;
for(int i = 0; i <= n; ++i){
if (i == 0) wayNums.push_back(1);
else if (i==1) wayNums.push_back(2);
else wayNums.push_back(dp[i - 1] + dp[i - 2]);
}
return dp.back();
}
跳跃游戏
leetcode给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例
1 | |
解题思路
- 动态规划：建立一个bool类型的dp数组用来记录每个格子是否能够到达
- 当前格子能否到达与它前面的每个格子都有关系，所以需要遍历它前面的所有格子，只要有一个格子本身能够到达且也能够跳到当前格子，则当前格子就能到达。
- 本体使用动态规划的时间复杂度比较大,主要用于培养动规的思想。
- 针对力扣提交的用例，在遍历当前格子之前的格子时，从后往前遍历不容易超时。
1
2
3
4
5
6
7
8
9
10
11
12
13bool canJump(vector<int>& nums) {
vector<bool> dp(nums.size(), false);
dp[0] = true;
for (int i = 1; i < nums.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (dp[j] == true && nums[j] >= i - j) {
dp[i] = true;
break;
}
}
}
return dp[nums.size()-1];
}
跳跃游戏II
leetcode给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
解题思路
- 如果要用动规的思想去解决，那么需要建立一个记录达到每个格子的最小跳跃次数的dp数组，
- 当前格子的最少次数 = 它前面所有能到达当前位置的格子的步数最小值 + 1，所以还是要遍历当前格子之前的所以格子，时间复杂度会相当高，超过时间限制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14int jump(vector<int>& nums) {
vector<int> dp(nums.size(),0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
int less = 0x3f3f3f3f;
for (int j = i-1; j >= 0; --j) {
if (j + nums[j] >= i) {
less = min(less, dp[j] + 1);
}
}
dp[i] = less;
}
return dp[nums.size()-1];
} - 还可以想办法继续优化，例如加上贪心的算法，因为既然有多个格子可以跳跃到当前格子，从最少跳跃次数的角度考虑，我当然希望是离当前格子最远的地方跳跃过来，也就是我们只需要正向遍历到第一个能够跳跃到当前格子的位置就行了。
- 当然用c++还是会超时间限制，可以用java
1
2
3
4
5
6
7
8
9
10int jump(vector<int>& nums) {
vector<int> dp(nums.size(),0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
int j = 0;
while (j < nums.size() && j + nums[j] < i) j++;
dp[i] = dp[j] + 1;
}
return dp[nums.size()-1];
}
分割回文串 II
leetcode给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例
1 | |
解题思路
- 首先建立dp数组，记录每到一个字母，和它前面所组成的字符串，能使每个子串都是回文串最少分割次数。
- 动态规划的思路就是，找到当前
dp[i]的值与dp[i-1]、dp[i-2].....有怎么的联系 - 对于本题，通过遍历
i之前的所有下标j，找到所有能和i组成回文串的j下标，在这么多能和i组成的回文串的j下标中，通过比较找出最少分割数的dp[j],再+1就是当前位置dp[i]的值. - 如果一整个串就是一个回文串，那么最小分割数自然为0
- 下面的代码会超时，主要学习动规的思路，可以通过优化判断回文串isPalindrome()的方法。这里只用了最简单的方式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int minCut(string s) {
vector<int> dp(s.size(), 0x3f3f3f3f);
dp[0] = 0;
for (int i = 1; s[i] != '\0'; ++i) {
if (isPalindrome(s, 0, i)){
dp[i] = 0;
continue;
}
for (int j = i; j >= 0; --j){
if (isPalindrome(s, j, i)){
dp[i] = min(dp[i], dp[j-1] + 1);
}
}
}
return dp[s.size()-1];
}
bool isPalindrome(string s, int left, int right) {
if(right == left) return true;
while (left < right) {
if (s[left] != s[right]) return false;
left++, right--;
}
return true;
}
打家劫舍
Leetcode 计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 在不触动警报装置的情况下，能够偷窃到的最高金额。
解题思路
- dp数组储存抢劫每户时的最大抢劫量，dp[i]表示抢到第i个房间时的最大抢劫量
- 因为不能相邻抢劫，所以如果抢劫了
i-1户，就不能抢劫第i户，或者是i-2户再加上当前户i dp[i]=max(dp[i-1],dp[i-2]+nums[i]);- dp数组第一个值和第二个值分别为
nums[0]和max(nums[0].nums[1])
1 | |
打家劫舍II
所有的房屋都围成一圈.
Leetcode
- 打劫问题升级版，因为是环形的，所以多了一个限制条件：
- 如果从第一户开始偷，那么最后一户就不能偷，下标:
0~n-2 - 如果从第二户开始偷，最后一户就可以偷，下标为:
1~n-1 - 环形问题分解为两条子序列，子序列使用动态规划，比较者最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int rob(vector<int>& nums) {
if(nums.size() == 0) return 0;
if(nums.size() == 1) return nums[0];
return max(rob(nums, 0, nums.size()-2),rob(nums, 1, nums.size()-1));
}
int rob(vector<int>&nums, int left, int right){
//根据left和right确定开辟dp数组的大小
int cnt = left - right + 1;
vector<int> dp;
//cur是dp数组的下标，不是nums的下标，cur从0，即dp的第一元素开始
for(int cur = 0; cur < cnt; cur++){
if (cur == 0) dp.push_back(nums[left]);
else if (cur ==1) dp.push_back(max(nums[left], nums[left + 1]));
else{//max里比的是dp数组里的值，不是nums数组的
dp.push_back(max(dp[cur - 1], dp[cur - 2] + nums[left + cur]));
}
}
return dp.back();
}
打家劫舍III
Leetcode在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
暴力递归
解题思路
- 树形动态规划问题
- 首先要明确相邻的节点不能偷，也就是’爷爷’选择偷，’儿子’就不能偷了，但是’孙子’可以偷
- 二叉树只有左右两个孩子，1个’爷爷’最多 2 个’儿子’，4 个’孙子’
- 4 个’孙子’偷的钱 + ‘爷爷’的钱 VS 两个’儿子’偷的钱 哪个组合钱多，就当做当前节点能偷的最大钱数
1 | |
建立dp缓存的动态规划
解题思路
- 我们发现’爷爷’在计算自己能偷多少钱的时候，同时计算了 4 个’孙子’能偷多少钱，也计算了 2 个’儿子’能偷多少钱。这样在’儿子’当’爷爷’时，就会产生重复计算一遍’孙子’节点
- 动态规划的关键优化点 ‘重复子问题’
- 使用的优化方案是记忆化，但是之前的问题都是使用数组解决的，把每次计算的结果都存起来，下次如果再来计算，就从缓存中取，不再计算了，这样就保证每个数字只计算一次。
- 由于二叉树不适合拿数组当缓存，我们这次使用哈希表来存储结果，TreeNode 当做 key，能偷的钱当做 value,记录每个计算过得结点值终极解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int rob(TreeNode* root) {
unordered_map<TreeNode*, int>dp;
return rob(root, dp);
}
int rob(TreeNode* root, unordered_map<TreeNode*, int> dp){
if (root == NULL) return 0;
if (dp.count(root) != 0) return dp[root];
int money=root->val;
if (root->left) money += rob(root->left->left, dp) + rob(root->left->right, dp);
if (root->right) money += rob(root->right->left, dp) + rob(root->right->right, dp);
int res = max(money,rob(root->left,dp) + rob(root->right, dp));
dp[root] = res;
return res;
}
解题思路
- 上面两种解法用到了’孙子’节点，计算’爷爷’节点能偷的钱还要同时去计算’孙子’节点投的钱
- 每个节点储存偷或者不偷两种状态得最大值
- 我们使用一个大小为 2 的数组来表示,下标0存不偷的值，下标1存偷的值
- 当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
- 当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
- 自下而上选择后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int rob(TreeNode* root) {
vector<int> res(2);
res = postOrder(root);
return max(res[0], res[1]);
}
vector<int> postOrder(TreeNode* root){
if (root == NULL) return {0,0};
vector<int> res(2);
vector<int> left = postOrder(root->left);
vector<int> right = postOrder(root->right);
res[0] = max(left[0], left[1]) + max(right[0], right[1]);
res[1] = root->val + left[0] + right[0];
return res;
}
三角形最小路径和
leetcode给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
示例
1 | |
解题思路
- 自顶向下，所以每一行的元素都与上一行的元素有关，第一行除外，所以遍历从第二行开始
- 建立dp数组，dp[i][j]表示到达此此处的最小路径和，dp数组中最后一行的最小值即为所求。
- 公式：每一项都与他的上一行有关
dp[i][j] = min(dp[i-1][j] + dp[i-1][j]) + triangle[i][j] - 需要考虑边界，因为时三角形的，例如每一行的第0个元素，他的上一行没有
0-1的元素;还有每一行的最后一个第i元素，他的上一行只有i-1这个元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
vector<vector<int>> dp(len,vector<int>(len,0x3f3f3f3f));
dp[0][0] = triangle[0][0];
for (int i = 1; i < len; ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) dp[i][j] = dp[i-1][j] + triangle[i][j];
else if (j == i) dp[i][j] = dp[i-1][j-1] + triangle[i][j];
else dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
}
}
sort(dp[len-1].begin(), dp[len-1].end());
return dp[len-1][0];
}解题思路
- 自底向上，所以每一个元素都与下一行的元素有关，最后一行除外，所以遍历从倒数第二行开始
- 公式：
dp[i][j] = min(dp[i+i][j], dp[i+1][j]) + triangle[i][j] - 因为是三角形，边界的元素在下一行必有相邻的元素存在，所以免去了边界检测。
1
2
3
4
5
6
7
8
9
10int minimumTotal(vector<vector<int>>& triangle) {
// 自底向上
// 从倒数第二行开始
for (int i = triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j < triangle[i].size(); ++j) {
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
最小路径和
leetcode给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例
1 | |
解题思路
- 上一题是三角形，这一题变矩形，首先考虑自左上角到右下角，那么每个元素的最小路径和都与他的上一个元素或者左边的元素有关，但是考虑到边界，第一列和第一行的元素并没有左或者上面的于元素，所以需要单独考虑，同时第一个元素左和上都没有，也需要单独考虑。
- 剩下的元素公式为：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];1
2
3
4
5
6
7
8
9
10
11
12
13
14int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> dp(row, vector<int>(col, 0x3f3f3f3f));
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (i == 0 && j > 0) dp[i][j] = dp[i][j-1] + grid[i][j];
else if (j == 0 && i > 0) dp[i][j] = dp[i-1][j] + grid[i][j];
else if (i == 0 && j == 0) dp[i][j] = grid[0][0];
else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[row-1][col -1];
}解题思路
- 如果是自右下至左上，对于本题仍然有边界需要考虑，每个元素的最小路径和都与他的右边和下边的值有关，但是对于最后一行和最后一列并没有下或者右边的值，需要单独考虑，最右下角的值右和下都没有，更需要单独考虑
- 对于其他元素,可以不用建立dp数组的方式实现，取他的右和下最小值相加：
grid[i][j] += min(grid[i+1][j], grid[i][j+1]);1
2
3
4
5
6
7
8
9
10
11
12
13int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
for (int i = row-1; i >= 0; --i) {
for (int j = col-1; j >= 0; --j) {
if (i == row-1 && j == col-1) continue;
else if (i == row-1) grid[i][j] += grid[i][j+1];
else if (j == col-1) grid[i][j] += grid[i+1][j];
else grid[i][j] += min(grid[i+1][j], grid[i][j+1]);
}
}
return grid[0][0];
}
不同路径
leetcode一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
解题思路
- 此题是上一题最小路径和的简易版,这里就只写了一种自右下至左上的思路
- 需要一个dp数组来记录到某个格子的所有路径个数，因为是自右下往左上，所以每个格子都可以从他的右边或者下面到达，所以这个格子的路径数就等于他下面和右边格子路径数之和。
- 大部分格子的公式:dp[i][j] = dp[i+1][j] + dp[i][j+1];但是又边界的考虑，例如最后一列和最后一行的格子没有右或者下面的格子，就必须单独考虑。最右下角的格子右边和下面都没有，更需要拎出来单独考虑了。
1
2
3
4
5
6
7
8
9
10
11
12int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0x3f3f3f3f));
for (int i = m-1; i >=0; --i) {
for (int j = n-1; j >= 0; --j) {
if (i == m-1 && j == n-1) dp[i][j] = 1;
else if (i == m-1) dp[i][j] = dp[i][j+1];
else if (j == n-1) dp[i][j] = dp[i+1][j];
else dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
不同路径 II
leetcode一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
示例
1 | |
解题思路
- 此题就体现出了从右下往左上建立dp表的优势，因为障碍物的出现只会影响上面和左边的格子，但是因为遍历的顺序是从右下往左上，所以一定是先遍历到障碍物的格子，之后才会遍历到被它所影响到的格子。
- 既然是先遍历到障碍物，那直接将其在dp数组中的路径数设为0，对于被他影响的格子就相当于此路不通，不走这个障碍物格子。
- 其他正常的格子路径还是：
dp[i][j] = dp[i+1][j] + dp[i][j+1]; - 对于两个边界：最后一列的格子:
dp[i][j] = dp[i+1][j];,最后一行的格子dp[i][j] = dp[i][j+1];1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<long>> dp(row,vector<long>(col,0x3f3f3f3f));
for (int i = row-1; i >=0; --i) {
for (int j = col-1; j >= 0; --j) {
if (obstacleGrid[i][j] == 1) {dp[i][j] = 0; continue;}
if (i == row-1 && j == col-1) dp[i][j] = 1;
else if (i == row-1) dp[i][j] = dp[i][j+1];
else if (j == col-1) dp[i][j] = dp[i+1][j];
else dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
最长上升子序列
leetcode给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
1 | |
解题思路
- 使用暴力法动态规划：定义dp[i] 为考虑前 i 个元素，必须以第 i个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取为最长上升子序列之中。
- 所以状态转移方程为:
dp[i] = max(dp[j], dp[j-1].......） + 1其中j表示i之前的所以元素。 - 因为是升序序列，j在i之前，所以一定
nums[j] < nums[i]才行。 - 注意返回值不在是
dp[nums.size()-1]，而是dp数组中的最大值，因为dp[i]代表的是以nums[i]为序列结尾的最长个数。实际最长的序列不一定是以最后一个数字nums[size()-1]为结尾的。 max_element()在头文件#include <algorithm>中，返回的是迭代器，所以输出值的话要在前面加 *,默认是从小到大排列.1
2
3
4
5
6
7
8
9
10
11
12int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size() , 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
单词拆分
leetcode给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例
1 | |
最长公共子序列
leetcode给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例
1 | |
解题思路
- 动规面试题高频题型，最长公共子序列（Longest Common Subsequence，简称 LCS）
- 对于子序列类型的问题，暴力点就是穷举问题，而动态规划算法做的就是穷举 + 剪枝，所以可以说只要涉及子序列问题，基本上就是动规解决
- 因为两个字符串就要建立一个dp table来解决，首先明白dp数组的含义是
dp[i][j]表示：对于s1[1..i]和s2[1..j]，它们的 LCS 长度是dp[i][j]。 - 由于两个字符串有可能其中一个是空串，所以dp数组还需要多加一列和一行，他们的dp[i][j]永远是0，因为是空串，永远不会有lcs。所以之后i和j的遍历时从1开始.szie()结束。
- 状态转移方程，二维的dp table，每个状态值都是由前面的三个状态影响：
dp[i][j] = (dp[i-1][j], dp[i][j-1], dp[i-1][j-1) - 还要明白，如果一个字母，两个串都有，那么他一定属于LCS，LCS长度就要+1。
- i和j指针所指的如果不相等，那么就取前面两个状态的最大值即可。
- 超详细原理请参考其他大佬的：动态规划之最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size();
int len2 = text2.size();
vector<vector<int> > dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 1; i < len1 + 1; ++i) {
for (int j = 1; j < len2 + 1; ++j) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
编辑距离
leetcode给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例
1 | |
解题思路
- 参考大佬的解题思路：powcai
dp[i][j]代表word1到i位置转换成word2到j位置需要最少步数- 当
word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]； - 当
word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 - 因为我们要将
word1变为word2,也就是用删除，增加，替换操作将word1的每个字母变成word2的字母 - 说明 更容易理解些： dp[i-1][j-1]到dp[i][j]需要进行替换操作，dp[i-1][j]到d[i][j]需要进行删除操作，dp[i][j-1] 到d[i][j]需要进行添加操作。
- dp table第一行，是
word1为空变成word2最少步数，就是插入操作 - 第一列，是
word2为空，需要的最少步数，就是删除操作
1 | |
零钱兑换
leetcode给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
解题思路
1 | |
最长回文子串
leetcode
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
解题思路
- 动态规划，要想知道长度为n的字符串是否是回文，需要先了解长度n-2的字符串是否是回文，同时首尾的字符也必须相等才行。
dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]表示从第i个字符开始到第j个字符结束- 判断长得字符串是否回文需要先判断短得字符串是否成立，所以必须从长度
len = 0开始遍历建立dp数组。 - 边界条件1，长度为1即len = 0时，一个字母一定是回文串，所以为true
- 边界条件2，长度为2即len = 1时，两个字母只有相等时才是true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n ,false));
string res;
int MAX = INT_MIN;
for (int len = 0; len < n; ++len) {
for (int i = 0; i + len < n; ++i) {
int j = i + len;
if (len == 0) dp[i][j] = true;
else if (len == 1) dp[i][j] = (s[i] == s[j]);
else dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
if (dp[i][j] && len + 1 > MAX) {
MAX = len + 1;
res = s.substr(i, len + 1);
}
}
}
return res;
}
