leetcode动态规划总结
为了准备三月份蓝桥杯的比赛和提高下自己数据结构和算法方面的水平，所以开始在leetcode上刷起了题。刚刚开始刷题的模式还是和之前一样，一道一道的按顺序的做过去，从easy到medium，但是发现这样的效率很低，因为每道题的考的知识点思路都不一样，很难去总结出相应数据结构和算法的知识体系和框架。因此我去网上查了下如何刷leetcode效率会比较高，发现很多人都推荐刚开始按标签刷会比较好，因为标签下面包含的是同一类算法或数据结构的题型，做起来方便总结相关知识。我想了下的确是这样，所以选择了动态规划这个标签开始刷起。动态规划我也只是之前有所听闻，直到开始刷题才开始慢慢了解其内容，题也刷了十几道，下面就回顾下这些题的做法和解题思想，也算是对动态规划一个小小总结吧，毕竟温故而知新嘛。
动态规划
在开始之前，先介绍下什么是动态规划、动态规划主要解决什么问题以及动态规划的步骤。
什么是动态规划？动态规划解决什么问题?
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。（来自百度百科）
动态规划步骤
1、拆分问题：看看问题是否能拆分成若干个子问题，从而通过解决子问题得到整个问题的解。（自顶向下）
2、找出子问题间的的关联，从而将其状态转移方程确定（自底向上，最难的一步）
3、解决问题（用数组或变量将其状态存储，并进行递归求解）
空谈误国，实干兴邦。下面开始对题目进行分析和总结，从中了解动态规划的奥妙。
Leetcode动态规划习题分析和总结
5.最长回文子串（medium）
这道题是开始刷的第一道题，开始真是一点思路都没有，只有用暴力解将其子串一个个求出并将其子串进行回文判断，若是回文则将其大小输出并与当时maxSize进行比较。暴力解的时间复杂度应该达到了O(n^3),因超出时间现在无法通过。
class Solution {
public:
string longestPalindrome(string s) {
string res, temp;
int size = 0;
for(int i = 0; i < s.size(); i++)
{
if(s.size() - i <= size)
{
break;
}
for(int j = i; j < s.size(); j++)
{
temp +=s[j];
int tSize = isPalindrome(temp);
if(tSize > size)
{
res = temp;
size = tSize;
}
}
temp.clear();
}
return res;
}
int isPalindrome(string s)
{
int size = s.size();
for(int i = 0, j = size - 1; i <= j; i++, j--)
{
if(s[i] != s[j])
{
return -1;
}
}
return size;
}
};
之后看了官方题解，可以利用动态规划的思想可以对暴力解进行改进。看到该方法不禁感叹，感觉打开了新世界的大门啊简直是。这题解也说明了，动态规划其一目的是避免不必要的重复计算。
动态规划采用了二维数组来表示子串的回文状态，例如dp[i][j]表示字符串第i个字母到第j个字母组成的子串是否是回文，是则为true，否则为false。dp[i][j]是否为回文与dp[i+1][j-1]状态有关，由此也可以推导出状态转移方程。而需先初始化一字母回文和二字母回文是为单数字符串和双数字符串做铺垫。
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int max = 1;
int fj = 0;
for(int i = 0; i < s.size(); i++) //初始化一字母和二字母回文
{
dp[i][i] = true;
if(i+1 != s.size())
{
if(s[i] == s[i+1])
{
dp[i][i+1] = true;
max = 2;
fj = i;
}
}
}
for(int i = 2; i < s.size(); i++) //输出的矩阵应为一个上三角矩阵
{
for(int j = 0; j < i-1; j++)
{
if(dp[j+1][i-1] && s[i] == s[j])
{
dp[j][i] = true;
int tempSize = i - j + 1;
if(tempSize > max)
{
max = tempSize;
fj = j;
}
}
}
}
return s.substr(fj, max);
}
因需遍历一个上三角矩阵，故动态规划方法的时间复杂度为O(n^2)。
解决这个问题还有一个方法就是中心扩展算法，他是以一个或两个字母为中心向两边进行扩展进而判断回文，该较为简单，看官方题解即可。
class Solution {
public:
string longestPalindrome(string s) {
int start = 0, end = 0;
int maxSize = 0;
string res;
for(int i = 0; i < s.size(); i++) //以每个字母为中心进行遍历
{
int len1 = expendCenter(s, i, i); //单数字符串长度回文判断
int len2 = expendCenter(s, i, i+1);//双数字符串长度回文判断
int maxlen = max(len1, len2);
if(maxlen > maxSize)
{
maxSize = maxlen;
start = i - ((maxlen - 1) /2);
end = i + (maxlen/2);
}
}
for(int i = start; i <= end; i++)//此处可用string方法中substr代替
{
res += s[i];
}
return res;
}
int expendCenter(string s, int left, int right)
{
while(left >= 0 && right < s.size() && s[left] == s[right])
{
left--;
right++;
}
return right - left - 1;
}
};
时间复杂度O(n^2)。
53.最大子序和（easy）
用动态规划思想定义一个概念，f(k)表示以当前元素结尾的子数组的最大值，其实这f(k)里面包含了两种状态，一种是连续状态，一种是不连续状态（即重新计算字数组最大值），取这两种状态的最大值作为f(k)的值，故则f(k)应该等于max(num[k],f(k-1)+num[k])。代码如下
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp_1 = nums[0];
int res = dp_1;
for(int i = 1; i < nums.size(); i++)
{
dp_1 = max(dp_1+nums[i], nums[i]);
res = max(dp_1,res);
}
return res;
}
};
62.不同路径（medium）
由题意可以知道到达一个格子只有两种路以可以选择，向下或者向右，由此我们可以得出dp[i][j] = dp[i-1][j] + dp[i][j-1],即到达坐标为（i，j)格子的路径数量等于到达坐标（i-1，j)(目标各格子左边的格子）的路径数量加上到达坐标（i，j-1)(目标各格子左边的格子）的路径数量。显然第一行和第一列的路径数量为1，所以需将网格到达第一行和第一列的路径数量全部初始化为1。
class Solution {
public:
int uniquePaths(int m, int n) {
int steps[100][100] = {-1};
for(int i = 0; i < 100; i++)
{
steps[0][i] = 1;
steps[i][0] = 1;
}
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
steps[i][j] = steps[i-1][j] + steps[i][j-1]; //状态转移
}
}
return steps[m-1][n-1];
}
};
时间复杂度为O(n^2)。
63.不同路径II(medium)
思路和不同路径一样，只不过注意处理一些特殊情况即可
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
long steps[100][100] = {0};
for(int i = 0; i < obstacleGrid.size(); i++)
{
if(obstacleGrid[i][0] == 1)
{
break;
}
steps[i][0] = 1;
}
for(int i = 0; i < obstacleGrid[0].size(); i++)
{
if(obstacleGrid[0][i] == 1)
{
break;
}
steps[0][i] = 1;
}
for(int i = 1; i < obstacleGrid.size(); i++)
{
for(int j = 1; j < obstacleGrid[0].size(); j++)
{
if(obstacleGrid[i][j] == 1)
{
continue;
}
if(obstacleGrid[i-1][j] == 1 && obstacleGrid[i][j-1] == 1)
{
steps[i][j] = 0;
}
if(obstacleGrid[i][j-1] == 1 && obstacleGrid[i-1][j] != 1)
{
steps[i][j] = steps[i-1][j];
}
if(obstacleGrid[i-1][j] ==1 && obstacleGrid[i][j-1] != 1)
{
steps[i][j] = steps[i][j-1];
}
if(obstacleGrid[i-1][j] == 0 && obstacleGrid[i][j-1] == 0)
{
steps[i][j] = steps[i-1][j] + steps[i][j-1];
}
}
}
return steps[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
}
};
时间复杂度为O(M*N)。
64.最小路径和（medium）
思路和前面两道题差不多，只不过状态转移方程需要修改一下,该题的状态转移方程为grid[i][j] += min(grid[i-1][j], grid[i][j-1])，即坐标(i,j)最小路径等于坐标（i-1，j)和坐标（i,j-1)中较小的值加上当前网格的值。该题有个精选题解讲的比较好，截图记录一下。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for(int i = 1; i < grid.size(); i++)
{
grid[i][0] += grid[i-1][0];
}
for(int i = 1; i < grid[0].size(); i++)
{
grid[0][i] += grid[0][i-1];
}
for(int i = 1; i < grid.size(); i++)
{
for(int j = 1; j < grid[0].size(); j++)
{
grid[i][j] += grid[i-1][j] > grid[i][j-1] ? grid[i][j-1] : grid[i-1][j];
}
}
return grid[grid.size()-1][grid[0].size()-1];
}
};
时间复杂度为O(n^2)
91.解码方法（medium）
因为一共有26个字母，对应的编码为126，所以有两种解码方法。第一种解码方法是单个数字解码为一个字母(19，0除外），第二种是两个数字组合一同解码为一个字母(10~26）。所以求长度为n的编码的解码方法可以将其拆解为求长度为n-1的编码的解码方法（单个数字解码）和长度为n-2的编码方法（两个数字组合解码）。故状体转移方程dp[i] = dp[i-1]+dp[i-2]。当然，针对一些边界情况和特殊情况还得做一些处理，具体可以看代码。该题可利用字符’1‘，’2‘，’0‘巧妙去判断边界和数字组合情况，无需转成整数在做相关判断。
class Solution {
public:
int numDecodings(string s) {
if(s[0] == '0') return 0;
int ppre = 1, pre = 1; //n-2, n-1数量值，初始化为1
for(int i = 1; i < s.size(); i++)
{
int temp = pre;
if(s[i] == '0')//n为0
{
if(s[i-1] == '1' || s[i-1] == '2')//查看n-1是否是’1‘或’2‘，不是则无法被解码。是则为两个数字组合解码。
{
pre = ppre;
}
else
{
return 0;
}
}
else
{
if((s[i-1] == '1') || (s[i-1] == '2' && (s[i]>'0' && s[i]<'7'))) //保证字符在可被解码范围内
{
pre = pre + ppre;
}
}
ppre = temp;
}
return pre;
}
};
显然，时间复杂度为O(n)。
96.不同的二叉搜索树（medium）
该题官方题解写的挺详细的，故直接搬运过来。当时看完题解真的是有茅塞顿开的感觉，没想到可以利用长度去做函数用于状态转换。
95.不同的二叉树搜索树II（medium）
这题其实思路和上面那道题是一样的，不过这题多了个需要构建树的步骤。在构建树的过程中注意，左子树可以被重复利用，而右子树则需复制后每个节点加上节点值即完成右子树每个节点数值的偏移。
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<vector<TreeNode*>> trees(n+1);
if(n!=0)
{
trees[0].emplace_back(static_cast<TreeNode*>(NULL));
trees[1].emplace_back(new TreeNode(1)) ;
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
for(TreeNode* leftTree : trees[j-1])
{
for(TreeNode* rightTree : trees[i-j])
{
TreeNode* root = new TreeNode(j);
root->left = leftTree;
root->right = cloneRightTree(j, rightTree);
trees[i].push_back(root);
}
}
}
}
return trees[n];
}
//选用递归的方式进行树的复制
TreeNode* cloneRightTree(int offset, TreeNode* original)
{
if(original == NULL)
{
return NULL;
}
TreeNode* clone = new TreeNode(original->val+offset);
if(original->left != NULL)
{
clone->left = cloneRightTree(offset, original->left);
}
if(original->right != NULL)
{
clone->right = cloneRightTree(offset, original->right);
}
return clone;
}
};
120.三角形最小三角路径和（medium）
感觉这题状态转移方程挺容易看出来的。第i，j点可以有两种路径到达，故dp[i][j]表示三角矩阵总第i行第j个数，状态转移方程为dp[i][j] = min(dp[i-1][j-1]+dp[i][j], dp[i-1][j]+dp[i][j]),即选择最小路径为dp[i][j]的值。该思路对三角形来说是自顶向下，所以需做下边界处理
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for(int i = 1; i < triangle.size(); i++)
{
for(int j = 0; j < triangle[i].size(); j++)
{
if(j == 0) //左边界处理
{
triangle[i][j] = triangle[i-1][0] + triangle[i][j];
}
else if(j == triangle[i].size()-1) //右边界处理
{
triangle[i][j] = triangle[i-1][triangle[i-1].size()-1] + triangle[i][j];
}
else
{
triangle[i][j] = (triangle[i-1][j-1] + triangle[i][j]) < \
(triangle[i-1][j] + triangle[i][j]) ? \
(triangle[i-1][j-1] + triangle[i][j]) :
(triangle[i-1][j] + triangle[i][j]);
}
}
}
int min = 99999;
for(int i = 0; i < triangle[triangle.size()-1].size(); i++) //在最下方找出最小值
{
if(min > triangle[triangle.size()-1][i])
{
min = triangle[triangle.size()-1][i];
}
}
return min;
}
};
时间复杂度显然O(n^2)。
139.单词拆分（medium）
刚开始想到的是比较暴力的解法，刚做的写出来的时候还觉得用了动态规划的思想，现在回看发现并没有用到，只是单纯的暴力解而已。这个暴力解思路是这样的，先找出从字符串起始位置开始包含在字典里面的单词，找到后便将其下标数组置1表示其为第一次寻找到字典中的单词下标位置。之后便开始遍历下标数组，当寻找到下标数组不为0的下标位置i时，便从字符串中提取[i+1,n]范围内以i+1为起始下标的连续的子串，并逐次在字典中寻找是否有相同的子串。以此类推，当下标数组最后一位不为0时，则说明该字符串可以拆分，反之则不能。有点类似BFS的方法。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<int> wordIndex(s.size(), 0);
string cmpstr = "";
for(int i = 0; i < s.size(); i++) //找出第一次字典中含有的单词
{
cmpstr += s[i];
for(int j = 0; j < wordDict.size(); j++)
{
if(cmpstr.compare(wordDict[j]) == 0)
{
wordIndex[i] = 1;
}
}
}
for(int i = 0; i < wordIndex.size(); i++) //遍历下标数组
{
cmpstr = "";
if(wordIndex[i] != 0)
{
for(int j = i+1; j < s.size(); j++)//遍历子串
{
cmpstr += s[j];
for(int k = 0; k < wordDict.size(); k++)//与字典中比对
{
if(cmpstr.compare(wordDict[k]) == 0)
{
if(j == wordIndex.size()-1)
{
return true;
}
wordIndex[j] = wordIndex[i]+1;
}
}
}
}
}
if(wordIndex[wordIndex.size()-1] != 0)
{
return true;
}
return false;
}
};
若使用动态规划的思想则处理起来则相对比较简单，当时也是看了题解后才知道怎么才正确使用动态规划去做。下面是动态规划的官方题解，讲的比较详细，也将其如何拆分子问题的思路写了出来。动态规划给我的感觉就是逐个枚举，往后递推的过程。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> works;
vector<bool> dp(s.size()+1, false);
dp[0] = true; //相当于空字符串，这个处理很妙，解决了子串全长检查的问题
for(int i = 0; i < wordDict.size(); i++)
{
works.insert(wordDict[i]);
}
for(int i = 1; i <= s.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(dp[j] && (works.find(s.substr(j, i-j)) != works.end())) //dp[j]表示（0，j),已经在前面遍历中检查过，检查j到i是否在字典中符合，有则可拆分
{
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
这题将字典可将字典中的单词加进哈希表中，哈希表查找的时间复杂度为O(1),此题解时间复杂度为O(n^2)。
152.乘积最大子序列（medium）
这个应该还是比较容易想到思路的，主要是正数乘负数，负数乘正数时，最大会变最小，最小会变最大，所以要针对这个情况进行处理。令imax为当前最大值，则imax = max(imax * nums[i], nums[i]), 并且由于有上述情况出现，所以还要维护一个最小值的变量，并当nums[i]是负数是，交换最大和最小值再进行计算。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max = nums[0], imin = nums[0], imax = nums[0];
for(int i = 1; i < nums.size(); i++)
{
if(nums[i] < 0)
{
int sw = imax;
imax = imin;
imin = sw;
}
imax = imax*nums[i] > nums[i] ? imax*nums[i] : nums[i];
imin = imin*nums[i] < nums[i] ? imin*nums[i] : nums[i];
max = imax > max ? imax : max;
}
return max;
}
};
时间复杂度为O(n)
198.打家劫舍（easy）
当小偷在第i间房间时，其实他有两种状态，偷或者不偷，当他选择偷时，他肯定没有偷上一间房子，当他选择不偷时，他当前的钱和在上一间屋子时一样，所以设f(k)为重前k个房屋中能抢到的最大数额，则状态转移方程为f(k) = max(f(k-1), f(k-2)+当前屋子的钱）。
class Solution {
public:
int rob(vector<int>& nums) {
int preMax = 0; // k-2
int curMax = 0;// k-1
for(int num : nums)
{
int temp = curMax;
curMax = max(preMax+num, curMax);
preMax = temp;
}
return curMax;
}
};
时间复杂度为O(n)。
213.打家劫舍II(medium)
此题跟上一题不同之处在于，其房屋是循环的，即首尾相连。我们可以从题意得知，偷得了第一家就无法偷最后一家，偷最后一家就无法偷第一家。所以当我们偷第一家时，就将最后一家去掉，此时得解法和上一题一模一样。偷最后一家也同理可得。最后比较这两种情况得大小选最优的那个即可得出答案。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
int maxs[4] = {0};
for(int i = 0; i < nums.size()-1; i++)
{
int temp = maxs[1];
maxs[1] = max(maxs[0]+nums[i], maxs[1]);
maxs[0] = temp;
}
for(int i = 1; i < nums.size(); i++)
{
int temp = maxs[3];
maxs[3] = max(maxs[2]+nums[i], maxs[3]);
maxs[2] = temp;
}
return max(maxs[1], maxs[3]);
}
};
时间复杂度为O(n)。
221.最大正方形(medium)
这道题刚开始选择了滑动窗口这种比较暴力的解法,滑动窗口逐渐变大，并且在矩阵内滑动并判断是否为正方形。当时根本没有动态规划做法的思路。
//滑动窗口暴力解法
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0) return 0;
int minSize = matrix.size() < matrix[0].size() ? matrix.size() : matrix[0].size();
int flag;
int max = 0;
for(int i = 0; i < minSize; i++)
{
for(int j = 0; j+i < matrix.size(); j++)
{
for(int k = 0; k+i < matrix[0].size(); k++)
{
flag = 0;
for(int q = j; q <= j+i; q++)
{
for(int p = k; p <= k+i; p++)
{
if(matrix[q][p]!='1')
{
flag = 1;
break;
}
}
if(flag == 1)
{
break;
}
}
if(flag == 0 && i >= max)
{
max = i+1;
}
}
}
}
return max*max;
}
};
这题动态规划我也不太懂怎么去将其解释清楚，力扣里面有个题解讲解的挺清楚的：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/。这个题解里面将状态转移方程解释的比较清楚
若某格子值为 1 ，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。
而其图解也清楚的解释了取最小值的原因
来自于lzhlyle的题解
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0)return 0;
int col = matrix[0].size();
int pre = 0;
int max = 0;
vector<int> dp(col+1, 0);
for(int i = 0; i < matrix.size(); i++)
{
pre = 0;
for(int j = 1; j <= col; j++)
{
if(matrix[i][j-1] == '1')
{
int temp = dp[j];
dp[j] = min(min(dp[j-1], dp[j]), pre)+1;
pre = temp;
if(dp[j] > max)
{
max = dp[j];
}
}
else
{
dp[j] = 0;
}
}
}
return max*max;
}
};
时间复杂度为O(n^2)。
264.丑数（medium)
这里先说下丑数的定义先，只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6是丑数，因为它可以分解成2*3。由此定义我们可以知道位置在后面的丑数可以由位置在前的丑数得出（升序）。一开始我得解法是将前一个丑数分别乘以2，3，5，然后将其结果放入有序集合中，因为有序集合中得元素唯一且每次插入时会自动排序，故放入元素后选取最小的元素（即第一个元素）当作第n个丑数。
class Solution {
public:
int nthUglyNumber(int n) {
set<long> uglyNums;
long nums[1691];
nums[1] = 1;
for(int i = 2; i <= n; i++)
{
long mulTwo = nums[i-1]*2;
long mulThree = nums[i-1]*3;
long mulFive = nums[i-1]*5;
uglyNums.insert({mulTwo, mulThree, mulFive});
auto it = uglyNums.begin();
nums[i] = *it;
uglyNums.erase(it);
}
return nums[n];
}
};
这个可以利用三指针进一步去优化，也是利用动态规划的思想，不过指针是否前进跟当前的丑数有关，该方法利用三指针做到了提前排序，实在是秒啊！
class Solution {
public:
int nthUglyNumber(int n) {
long nums[1691] = {0};
nums[1] = {1};
int p2 = 1, p3 = 1, p5 = 1;
for(int i = 2; i <= n; i++)
{
nums[i] = min(nums[p2]*2,min(nums[p3]*3, nums[p5]*5));
if(nums[i] == nums[p2]*2) p2++;
if(nums[i] == nums[p3]*3) p3++;
if(nums[i] == nums[p5]*5) p5++;
}
return nums[n];
}
};
时间复杂度为O(n^2)
279.完全平方数（medium）
该题比较简单，思路也比较容易想到。设f(n)表示凑成n需要完全平方数的最小个数，所以可以得出状态转移方程为f(n) = min({f(n-完全平方数}）+ 1。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, 0);
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
int Min = 99999;
for(int j = 1; i-j*j >= 0; j++)
{
Min = min(dp[i-j*j], Min);
}
dp[i] = Min + 1;
}
return dp[n];
}
};
时间复杂度O(n^2)
300.最长上升子序列（medium）
这个应该算是比较经典动态规划的题目了，刚开始学习动态规划的时侯网上那些博客，答案都是用它来举例的，可是当我真正上手做这道题的时候还真的没想出来。其实现在回想一下也不算太复杂，力扣中krahets的题解对此题讲解的比较清楚。
krahets对最长子序列的题解
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
vector<int> dp(nums.size(), 1);
int Max = 1;
for(int i = 1; i < nums.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j])
{
dp[i] = max(dp[i], dp[j]+1);
}
}
if(dp[i] > Max)
{
Max = dp[i];
}
}
return Max;
}
};
时间复杂度为O(n^2)。
304.二维区域和检索-矩阵不可变（medium）
求矩阵中子矩阵的面积，我们定义dp[i][j]为左上角(0,0)到(i,j)的面积，所以（row1, clo1)到(row2,col2)的面积为S = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1]。
力扣官方题解
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix)
{
if(matrix.size() == 0) return;
dp = vector<vector<int>>(matrix.size()+1, vector<int>(matrix[0].size()+1, 0));
for(int i = 0; i < matrix.size(); i++)
{
for(int j = 0; j < matrix[0].size(); j++)
{
dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + matrix[i][j] - dp[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int res = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1];
return res;
}
vector<vector<int>> dp;
};
309.最佳买卖股票时机含冷冻期(medium)
这题我觉得是最能体现动态规划中状态这一概念的题了，力扣中labuladong的题解对这个题的状态讲的十分清楚，直接参考题解并加以思考即可感受到动态规划的妙处所在。
labuladong最佳买卖股票时机的题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp_i_0 = 0, dp_i_1 = INT_MIN, dp_pre_0 = 0; //相当于第0天
for(int i = 0; i < prices.size(); i++)
{
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1+prices[i]);
dp_i_1 = max(dp_i_1, dp_pre_0-prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
};
时间复杂度O(n^2)
小结
回头看了总结下做过的关于动态规划的题，觉得动态规划还是个挺有趣的思想。可能这东西听起来感觉挺复杂的，但其实动态规划就是一个穷举的过程，将所以可能列举出来，从中选择最优。最关键一步还是在于状态的选取和其转移方程，搞定这两步，接下来的问题也就迎刃而解了。所以动态规划问题主要有这几步：
1、拆分问题，确定状态，并用代码的形式表示状态
2、确定状态转移方程
3、求解问题。
求解动态规划问题步骤也可以参考一下该问题下王焱的题解。
该文章中图片均来自于力扣题解中，若有侵权请联系本人删除
