性质：重叠子问题，最优子结构
做了一些题，觉得最主要的思想就是随着规模增大，要存下每个子结构的值，子问题的结果是与上一个规模的更小子问题的结果相联系的，即重叠子问题。
70 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution {
public:
int climbStairs(int n)
{
/*递归，超时
if(n==1) return 1;
if(n==2) return 2;
return climbStairs(n-1)+climbStairs(n-2);
*/
if(n==1) return 1;
if(n==2) return 2;
int a=1,b=2,r=0;
for(int i=3;i<n+1;i++)
{
r=a+b;
a=b;
b=r;
}
return r;
}
};
首先此题同斐波那契数列是一样的。
斐波那契数列可以用递归做，但是超时。
又因为次题具有重叠子问题，最优子结构的性质。可以用动态规划做。
121 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()==0) return 0;
vector <int> result;
int low=INT_MAX;
int max = 0;
for(int i=0;i<prices.size();i++)
{
if(prices[i]<low)
{
low = prices[i];
}
result.push_back(prices[i]-low);
}
for(auto i:result)
{
if(i>max) max = i;
}
if(max>0) return max;
return 0;
}
};
- 遍历数组，当前值 减前面的最小值记录到一个数组中，最后数组的最大值就是结果。
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
- 总之就是在数组里挑数，挑出来的数的和最大，但是不能挑相邻的数
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> result;
if(nums.size()==0) return 0;
if(nums.size()==1)
{
return nums[0];
}
if(nums.size()==2)
{
return nums[0]>nums[1]?nums[0]:nums[1];
}
result.push_back(nums[0]);
result.push_back(nums[0]>nums[1]?nums[0]:nums[1]);
for(int i=2;i<nums.size();i++)
{
result.push_back((result[i-2]+nums[i]>result[i-1])?result[i-2]+nums[i]:result[i-1]);
}
return result.back();
}
};
- 一个数组result存子问题的状态
- result.push_back((result[i-2]+nums[i]>result[i-1])?result[i-2]+nums[i]:result[i-1]);
核心的算法，两种可能：1.选当前的那个数nums[i]，如果选了，就不能选nums[i-1]，即i-2的子问题(result[i-2])的结果+nums[i]，2.不选当前那个数i，即i-1子问题。看那个大，就是哪个。
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
class Solution {
public:
string longestPalindrome(string s) {
//dp[i][j]存的是子串i到j是否为回文串
vector<vector <int>>dp(s.size(), vector<int>(s.size()));
string result;
if(s.size()==0) return {};
for(int step=0;step<s.size();step++)
{//状态转移从步长为1慢慢变多
for(int i=0;i<s.size()-step;i++)
{
int j=i+step;
//步长为0时，只有一个元素，一定回文
if(step==0) dp[i][j] = 1;
//步长为1时，两个元素，相等即回文
else if(step==1) dp[i][j] = (s[i]==s[j]);
//步长>1时，有三个元素，如果首尾元素相等&&去掉首尾元素的子串回文，则回文
else dp[i][j] = dp[i+1][j-1] && s[i]==s[j];
//存下最大的回文子串
if(dp[i][j]&&result.size()<step+1) result = s.substr(i,step+1);
}
}
return result;
}
};
注意，状态转移的时候规模一定要从小到大。
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径
class Solution {
public:
int uniquePaths(int m, int n) {
//dp存start到i,j位置的路径（子问题）
vector<vector<int>> dp(m, vector<int>(n));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0)
{//第一列只有一种路径
dp[i][j]=1;
}
else if(j==0)
{//第一行只有一种路径
dp[i][j]=1;
}
//状态转移
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
此题跟上一题特别像。
当前块路径数等于上面块路径数+左边块路径数。
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
dp[0][1]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//障碍的块路径数为0
if(obstacleGrid[i-1][j-1]==1) dp[i][j]=0;
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};
类似还有第64题
