从递归到动态规划
只要调用一个递归函数，总有参数不可变和参数可变的部分
不可变的参数对结果没有影响因为都是一样的
分析一个递归函数得到结果依赖下层递归返回什么内容
为什么递归慢？因为会在不同的分支重复遍历相同的情况
递归到记忆化搜索
严格表结构的动态规划
解决重复遍历相同情况的问题
利用缓存实现递归函数的可变部分到缓存结果的映射
假如递归函数有k个参数可变，那么缓存的表具有k个维度
缓存表能区分是否计算过这个位置的内容，比如用INT MIN或者-1一类
缓存没命中的话就开始尝试，将尝试的结果存储到表中
时间复杂度O(缓存表的尺寸)，本来的复杂度是二叉树的节点数
计算动态规划表格
动态规划的顺序一定从递归函数的底层情况开始，或者说从递归的终止位置开始，知道不需要计算就直接出答案的位置
从上面的推导得出计算的顺序
利用递归函数的逻辑调用动态规划表格的内容
将调用下一级的递归函数更改为从下一级的递归函数的可变参数位置对应的缓存表的位置取出值
也就是将递归调用的过程变成从动态规划表格中取值的过程
小心越界
斜率优化
假如在递归的过程中出现枚举行为(比如计算一个格子的位置需要循环用到一系列从少到多的格子的信息)
那么可以考虑使用与这个格子临近的格子寻找不需要进行循环就可以直接常数时间内就得到结果的方法
leetcode 122题 买卖股票的最佳时机II
代码
class Solution {
public:
int maxTemp;
vector<int> profitCash;
vector<int> profitHold;
int maxProfit(vector<int>& prices) {
profitCash = vector<int>(prices.size(), 0);
profitHold = vector<int>(prices.size(), 0);
profitHold[0] = -prices[0];
for(int i = 1; i < prices.size(); i++)
{
profitCash[i] = max(profitHold[i-1]+prices[i], profitCash[i-1]);
profitHold[i] = max(profitCash[i-1] - prices[i], profitHold[i-1]);
}
return profitCash[prices.size()-1];
}
};思路：状态一共两种，此时持有股票或者此时不持有股票，每种有两种操作
持有的话要决定现在卖还是现在不卖，现在卖掉的话更新现在持有现金的最大利润（跟持有现金的前一天比较），否则维持现在持有股票的最大利润
不持有要决定现在买还是现在不买， 现在买的话更新现在持有股票的最大利润（跟持有股票的前一天比较），否则维持现在持有现金的最大利润。
leetcode 123.买卖股票的最佳时机III
与上一题类似，先给出递归的版本（超时）再给出转化为动态规划的版本
分析每一次持仓的时候的动作为减仓和维持不变，每一次没有持仓的时候的操作是加仓和维持不变，这样就可以给出每次状态转换的递归关系，进而通过函数的参数个数（递归函数有剩余交易次数，是否持仓，交易天数三个参数和当前的利润一个结果），给出一个三维数组。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2)return 0;
return max(trybuyAndSell(prices, 2, false, 0, 1), trybuyAndSell(prices, 1, true, -prices[0], 1));
}
int trybuyAndSell(vector<int>& prices, int remain, bool haveStock, int curProfit, int i)
{
if(i == prices.size()-1)
{
if(haveStock)return curProfit+prices[i];
else return curProfit;
}
if(!haveStock&&remain == 0)
{
return curProfit;
}
else if(haveStock)
{
return max(trybuyAndSell(prices, remain, true, curProfit, i+1), trybuyAndSell(prices, remain, false, curProfit+prices[i], i+1));
}
else if(!haveStock)
{
return max(trybuyAndSell(prices, remain-1, true, curProfit - prices[i], i+1), trybuyAndSell(prices, remain, false, curProfit, i+1));
}
return curProfit;
}
int maxProfit(vector<int>& prices)
{
int cnt = prices.size()-1;
if(prices.size()<2)return 0;
// 第一个维度是剩余次数，第二个是是否持仓，第三个是当前利润
vector<vector<vector<int>>> mat(3, vector<vector<int>>(2, vector<int>(prices.size(), INT_MIN)));
mat[1][1][0] = -prices[0];
mat[2][0][0] = 0;
for(int i = 1; i<=cnt; i++)
{
if(i>1)mat[0][1][i] = max(mat[1][0][i-1] - prices[i], mat[0][1][i-1]);
if(i>1)mat[0][0][i] = max(mat[0][0][i-1], mat[0][1][i-1]+prices[i]);
mat[1][1][i] = max(mat[2][0][i-1] - prices[i], mat[1][1][i - 1]);
mat[1][0][i] = max(i>1?mat[1][0][i-1]:INT_MIN, mat[1][1][i-1]+prices[i]);
// mat[2][1][i] = max(mat[])
mat[2][0][i] = mat[2][0][i-1];
}
return max(mat[2][0][cnt], max(mat[1][0][cnt], mat[0][0][cnt]));
}
};leetcode 97.交错字符串
其实不需要根据s3的长度建立很多个数组，因为s1和s2遍历到的位置能直接确定s3遍历到的字符，只用建立s1和s2长度为两边的二维数组即可。
class Solution {
public:
vector<vector<int>> v;
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() == 0)return s2 == s3;
else if(s2.size() == 0)return s1 == s3;
v = vector<vector<int>>(s1.size()+1, vector<int>(s2.size()+1, INT_MIN));
return tryIfPos(s1, s2, s3, 0, 0, 0);
}
bool tryIfPos(string&s1, string& s2, string& s3, int i1, int i2, int i3)
{
// cout<<i1<<' '<<i2<<' '<<i3<<endl;
if(v[i1][i2]!=INT_MIN)return v[i1][i2];
if(i1 == s1.size() && i2 == s2.size())
{
if(i3 == s3.size())
{
v[i1][i2] = true;
return true;
}
else
{
v[i1][i2] = false;
return false;
}
}
else if(i3 == s3.size())
{
v[i1][i2] = false;
return false;
}
bool temp1 = false, temp2 = false;
if(i1<s1.size()&&s3[i3] == s1[i1])
{
if(v[i1+1][i2] == INT_MIN)
temp1 = tryIfPos(s1, s2, s3, i1+1, i2, i3+1);
else temp1 = v[i1+1][i2];
}
if(i2<s2.size()&&s3[i3] == s2[i2])
{
if(v[i1][i2+1] == INT_MIN)
temp2 = tryIfPos(s1, s2, s3, i1, i2+1, i3+1);
else temp2 = v[i1][i2+1];
}
// cout<<'!';
if(!(s3[i3] == s1[i1] || s3[i3] == s2[i2]))
{
// if(i1<s1.size()&&i2<s2.size()&&i3<s3.size())
v[i1][i2] = false;
return false;
}
// cout<<'@';
// if(i1<s1.size()&&i2<s2.size()&&i3<s3.size())
v[i1][i2] = temp1||temp2;
return v[i1][i2];
}
};击败100%
leetcode 44.通配符匹配
将递归转化为动态规划的时候可以采用与递归相同的顺序，比如递归是前面引用后面的，那动态规划也可以写成倒序的方便转换
注意基础位置的条件
class Solution {
public:
bool isMatch(string s, string p) {
if(s.size() == 0)
{
for(int i = 0; i<p.size(); i++)
{
if(p[i]!='*')return false;
}
return true;
}
else if(p.size() == 0)return false;
vector<vector<bool>> m(s.size(), vector<bool>(p.size(), false));
int i = p.size()-1;
if(p[p.size()-1] == s[s.size()-1])
{
m[s.size()-1][p.size()-1] = true;
--i;
}
else if(p[p.size()-1] == '?'&&s.size()>0)
{
--i;
m[s.size()-1][p.size()-1] = true;
}
else if(p[p.size()-1] == '*')
{
for(int i = s.size()-1; i>=0; i--)
{
m[i][p.size()-1] = true;
}
}
else return false;
for(; i>=0; i--)
{
for(int si = s.size()-1; si>=0; si--)
{
if(s[si] == p[i] || p[i] == '?')
{
if(si<s.size()-1&&i<p.size()-1)
{
m[si][i] = m[si+1][i+1];
}
else if(si<s.size()-1&&i == p.size()-1)
{
m[si][i] = false;
}
else if(i<p.size()-1&&si == s.size()-1)
{
m[si][i] = true;
for(int k = i+1; k<p.size(); k++)
{
if(p[k]!='*')
{
m[si][i] = false;
break;
}
}
}
else
{
m[si][i] = true;
}
}
else if(p[i] == '*')
{
if(si<s.size()-1&&i<p.size()-1)
m[si][i] = m[si+1][i+1]|m[si+1][i]|m[si][i+1];
else if(si<s.size()-1&&i == p.size()-1)
{
m[si][i] = true;
}
else if(i<p.size()-1&&si == s.size()-1)
{
m[si][i] = m[si][i+1];
}
else
m[si][i] = true;
}
else m[si][i] = false;
}
}
return m[0][0];
}
bool starUtil(string& s, string& p, int i1, int i2)
{
if(s.size() == i1)
{
if(i2<p.size())
{
for(; i2<p.size(); i2++)
{
if(p[i2]!='*')
{
return false;
}
}
}
return true;
}
if(p[i2] == '*')
{
return starUtil(s, p, i1+1, i2)||starUtil(s, p, i1, i2+1)||starUtil(s, p, i1+1, i2+1);
}
else if(s[i1] == p[i2])
{
return starUtil(s, p, i1+1, i2+1);
}
else if(p[i2] == '?')
{
return starUtil(s, p, i1+1, i2+1);
}
else return false;
}
};leetcode 152.乘积最大子数组
注意按照最大和最小分类讨论，因为有正负的问题
class Solution {
public:
int maxProduct(vector<int>& nums) {
int maxI = INT_MIN;
vector<vector<int>> m(2, vector<int>(nums.size(), 0));
m[1][0] = nums[0];
m[0][0] = nums[0];
maxI = maxI>=m[0][0]?maxI:m[0][0];
maxI = maxI>=m[1][0]?maxI:m[1][0];
for(int i = 1; i<nums.size(); i++)
{
m[0][i] = min(nums[i], min(nums[i]*m[0][i-1], nums[i]*m[1][i-1]));
m[1][i] = max(nums[i], max(nums[i]*m[0][i-1], nums[i]*m[1][i-1]));
maxI = maxI>=m[0][i]?maxI:m[0][i];
maxI = maxI>=m[1][i]?maxI:m[1][i];
}
return maxI;
}
};
leetcode 238.除自身以外数组的乘积
- 因为不能用除法，所以使用两个数组，一个记录每个位置左侧位置的所有数字乘积，另一个记录右侧，没有元素的话认为是1
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> lProduct(nums.size(), 1);
vector<int> rProduct(nums.size(), 1);
for(int i = 0; i<nums.size()-1; i++)
{
lProduct[i+1] = nums[i]*lProduct[i];
rProduct[nums.size()-i-2] = nums[nums.size()-1-i]*rProduct[nums.size()-i-1];
}
vector<int>ret(nums.size(), 0);
for(int i = 0; i<nums.size(); i++)
{
ret[i] = lProduct[i]*rProduct[i];
}
return ret;
}
};leetcode 322. 零钱兑换
- 使用最少数目的零钱兑换到指定的面额
- 注意递归（或者动态规划的循环内外层）的次序是可以改变的，使用零钱作为外层循环和使用剩余需要兑换的额度作为外层循环，该位置的零钱选择作为内层循环要更快一些
- 要抓到递归的本质是把钱兑换完，而不是把硬币都用一遍
class Solution {
public:
vector<int> m;
int coinChange(vector<int>& coins, int amount)
{
auto cmp = [](int&a, int &b)->bool
{
return a>b;
};
sort(coins.begin(), coins.end());
m = vector<int>(amount+1, 10001);
m[0] = 0;
for(int i = 0; i<=amount; i++)
{
if(m[i]>10000)continue;
for(auto j = coins.begin(); j!=coins.end()&&*j<=amount-i; j++)
{
m[i+*j] = min(m[i+*j], m[i]+1);
}
}
return m[amount]>10000?-1:m[amount];
}
};leetcode 334. 递增的三元子序列
- 这题主要是使用两个数组记录每个位置的左侧的最小值和右侧的最大值，找到某个位置的左侧的最小值小于自身和右侧的最大值大于自身的位置即可，此时只需要遍历两次，一次找每个位置左右侧的最值，一次找是否存在符合的点。
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
if(nums.size()<3)return false;
else if(nums.size() == 3)
{
if(nums[0]<nums[1]&&nums[1]<nums[2])return true;
else return false;
}
vector<int> lMin(nums.size());
lMin[0] = nums[0];
vector<int> rMax(nums.size());
rMax[nums.size()-1] = nums[nums.size()-1];
int nSize = nums.size();
for(int i = 1; i<nSize; i++)
{
lMin[i] = min(nums[i], lMin[i-1]);
rMax[nSize-1-i] = max(rMax[nSize-i], nums[nSize-1-i]);
}
for(int i = 1; i<nSize-1; i++)
{
if(lMin[i-1]<nums[i]&&rMax[i+1]>nums[i])return true;
}
return false;
}
};leetcode 413. 等差数列划分
- 寻找的是一个数组中，最小长度为3（可以超过3）的所有子数组的数量之和
- 比如一个数组跟以他的前一个数字结束的等差数列的公差相同，那么假如前一个数字结束的等差数列的最长长度为
k-2(k>=3)，那么以这个数字结束的数组的个数就是k+1-2，比如前一个数字结束的数组长度为5，那么以这个数字结束的数组的长度分别是3, 4, 5, 6共4种，正好是5+1-2class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
if(nums.size()<3)return 0;
else if(nums.size() == 3)
{
if(nums[0] - nums[1] == nums[1] - nums[2])return 1;
else return 0;
}
int i = 2;
while(i<nums.size()&&nums[i] - nums[i-1] != nums[i-1] - nums[i-2])++i;
if(nums[i] - nums[i-1] != nums[i-1] - nums[i-2])return 0;
vector<int> diffArr(nums.size(), 0);
vector<int> lengthArr(nums.size(), 0);
diffArr[1] = nums[i] - nums[i-1];
diffArr[2] = nums[i] - nums[i-1];
lengthArr[2] = 1;
int cnt = 1;
i+=1;
for(;i<nums.size(); i++)
{
int temp = nums[i] - nums[i-1];
diffArr[i] = temp;
if(temp == diffArr[i-1])
{
lengthArr[i] = lengthArr[i-1]+1;
cnt+=lengthArr[i];
}
}
return cnt;
}
};leetcode 300. 最长递增子序列
- 设置一个记录数组，记录以每个位置结尾的最长递增数组的长度
- 此题不能改变原来数组的排序，在原来数组中寻找一个递增的子序列（不需要连续）
- 遍历的方式是指定当前递增序列的结尾数字，在当前位置之前寻找一个比他小但是以这个位置结尾的数组最长的位置，将以当前位置结尾的递增数组的长度修改为前面选定的位置的递增数组的长度+1
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// int maxLen = 0;
int n = nums.size();
vector<int> lenArr(n, 1);
vector<int> ret;
int maxEnd = 0;
int maxLen = 1;
for(int i = 1; i<n; i++)
{
for(int j = 0; j<i; j++)
{
if(nums[j]<nums[i])
{
lenArr[i] = max(lenArr[i], lenArr[j]+1);
if(lenArr[i]>maxLen)
{
maxLen = lenArr[i];
maxEnd = i;
}
}
}
}
return maxLen;
}
};leetcode 368.最大整除子集
- 此题是在一个数组中寻找一个子数组（不需要连续，而且可以改变原来的数组的顺序），数组中的每个元素都能被上一个元素整除，寻找总长度最长的子数组
- 给出一个与原来的数组大小相同的长度记录数组（以当前位置作为最后一个元素的整除数组的最大长度）
- 首先将数组从小到大排序
- 然后在0位置给出当前位置的最长整除数组为1
- 然后以第
i个元素为末尾，遍历比这个元素小的所有元素，寻找能整除第i个元素而且以该数字结尾的数组最长的位置，将i位置的以该位置结束的数组的最大长度设置为前面找到的最长数组的长度+1 - 因为无法确定每个位置的数字是否需要，所以要以
n^2的时间复杂度遍历 - 回溯寻找这个最长的数组的时候，从当前最长数组的结尾元素的前一个元素开始，假如这个元素能整除当前的结尾元素，并且以这个元素结尾的数组的长度恰好是
最大长度-1，那么这个元素就是待求数组当前结尾元素的前一个元素，将其替换为当前待求的结尾元素，将最大长度-1，重复上述过程。class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
if(nums.size()<2)return vector<int>(nums);
sort(nums.begin(), nums.end());
int maxLen = 0, n = nums.size();
int maxEnd = 0;
vector<int> lenArr(n, 0);
vector<int>ret;
vector<vector<int>> m(n);
for(int i = 1; i<n; i++)
{
for(int j = 0; j<i; j++)
{
if(nums[i]%nums[j] == 0)
{
lenArr[i] = max(lenArr[i], lenArr[j]+1);
if(maxLen<lenArr[i])
{
maxLen = lenArr[i];
maxEnd = i;
}
}
}
}
int temp = nums[maxEnd];
ret.push_back(nums[maxEnd--]);
while(maxEnd>=0)
{
if(temp%nums[maxEnd] == 0&&lenArr[maxEnd] == maxLen-1)
{
ret.insert(ret.begin(), nums[maxEnd]);
temp = nums[maxEnd];
--maxEnd;
--maxLen;
}
else
{
--maxEnd;
}
}
return ret;
}
};牛客 HJ77 火车进站
- 链接
- 此题的主要回溯逻辑就是是否弹出栈中元素，可以弹出后再插入当前元素，或者不弹出直接插入
- 注意防止重复，一层递归只能插入一次
using namespace std;
vector<vector<int>> ans;
void traversal(vector<int>& v, stack<int> s, int beg, vector<int>& res)
{
if(beg == v.size())
{
stack<int> ts;
int toPop = s.size();
while(s.size())
{
res.push_back(s.top());
ts.push(s.top());
s.pop();
}
ans.push_back(res);
for(int i = 0; i< toPop; ++i)
{
res.pop_back();
}
while(ts.size())
{
s.push(ts.top());
ts.pop();
}
return ;
}
if(s.size())
{
int tmp = s.top();
res.push_back(tmp);
s.pop();
traversal(v, s, beg, res);
s.push(tmp);
res.pop_back();
}
s.push(v[beg]);
traversal(v, s, beg+1, res);
s.pop();
}
int main() {
int n;
cin>>n;
vector<int> v(n);
for(int i = 0; i<n; ++i)
{
cin>>v[i];
}
stack<int> s;
vector<int> a;
traversal(v, s, 0, a);
sort(ans.begin(), ans.end(), [](vector<int>&a, vector<int>&b) -> bool
{
for(int i = 0; i<a.size(); ++i)
{
if(a[i]!=b[i])return a[i]<b[i];
}
return false;
});
for(auto & r : ans)
{
for(auto i : r)
{
cout<<i<<' ';
}
cout<<endl;
}
}
// 64 位输出请用 printf("%lld")