leetcode今日两题-动态规划（1）
313、超级丑数
原题链接：”https://leetcode-cn.com/problems/super-ugly-number/"
本题此处提供两种解法，Key:新的丑数=旧的丑数Xprimes序列中的数。
1.优先队列+哈希集合
- 先将1加入最小堆
- 然后将堆顶元素弹出
- 用该元素乘上primes中所有数并将其加入堆中
- 由于会出现重复，所以使用哈希集合来去重
- 重复以上234步骤n次
(ps:也可以用底层为红黑树的set来一步到位，但效率较差，经比较大概比以上方法慢了一倍)
以下为代码实现：
typedef long long ll;
using namespace std;
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
unordered_set<ll>s;
priority_queue<ll, vector<ll>, greater<ll> >q;//最小堆，记得greater那要留多个空格
q.push(1);
s.insert(1);
ll cnt;
for(int i=0;i<n;i++){
cnt=q.top();
q.pop();
for(auto e:primes){
ll temp=cnt*e;//用long long是因为这一步有可能爆精
if(s.find(temp)==s.end()){//哈希集合的find方法，找不到即返回s.end()
q.push(temp);
s.insert(temp);
}
}
}
return cnt;
}
};时间复杂度约为$O(mnlogn)$
2.动态规划（非严谨）
核心：用multi数组决定要序列中的数要乘哪个旧丑数
为了保证预备丑数序列的递增性，所以要用尽量小的旧丑数去乘primes中的数，但之前生成过丑数的组合不能再相乘，因此其要向前进一，multi数组储存的是primes数组中对应数字在这次计算中需要相乘的旧丑数的index。
同时由于丑数序列的递增性，如果出现重复必然是与前一个数重复，所以通过简单的判断即可排除重复情况
下面是代码实现：
typedef long long ll;
using namespace std;
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int m=primes.size();
vector<ll>dp(n+10);
vector<ll>multi(m,1);
dp[1]=1;
int i=1;
while(i<=n){
ll minv=INT_MAX,temp;
int pos=0;
for(int j=0;j<m;j++){
temp=dp[multi[j]]*primes[j];//旧丑数乘primes中数
if(minv>temp){//找最小值
minv=temp;pos=j;//获取生成该丑数对应primes中的数字
}
}
if(dp[i]!=minv)//避免重复
dp[++i]=minv;
multi[pos]++;//关键
}
return dp[n];
}
};经检验，该方法时间复杂度为$O(mn)$，但实测比第一种快了好几倍。
446、等差数列划分
原题链接：”https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/"
序列dp
弱等差子序列：一个序列中至少有两个元素，并且任意两个相邻元素之差相同。（显然任何一对元素都满足）
状态描述：dp[i][d]表示以nums[i]为结尾，公差为d的弱等差子序列个数。dp[i]应该是一个「集合」，该集合记录下了所有以nums[i]为结尾，差值为所有情况的子序列的个数。
推导：设i,j（j < i）来做二重循环，其中nums[i]为子序列结尾，nums[j]为倒数第二。循环的目的是对于每个i,枚举区间[0, i - 1]的所有数。枚举当前位置前面的所有位置的目的，是为了找到当前位置的数，能够接在哪一个位置的后面，形成序列。
对于每个i,j，记d=nums[i]-nums[j],需要去找dp[j][d]，因为将nums[i]插到以nums[j]结尾的子序列中，构成以nums[i]为结尾的子序列，再nums[j],nums[i]也构成一个弱等差子序列，因此得出转移方程：$dp[i][d]+=dp[j][d]+1$;
而因为差值d有可能会过大爆精，但差值本身的数量是有限的，因此选用longlong和哈希map,至于答案便是递推过程中dp[j][d]的求和
代码实现如下：
typedef long long ll;
using namespace std;
class Solution {
public:
ll numberOfArithmeticSlices(vector<int>& nums) {
ll ans{0LL},cnt;
int l=nums.size();
vector<unordered_map<ll,int>>dp(l);//哈希map快
for(int i=0;i<l;i++){
for(int j=0;j<i;j++){
ll d=1LL*nums[i]-nums[j];//可能爆精
auto it=dp[j].find(d);//找是否有dp[j][d]
if(it!=dp[j].end())cnt=it->second;
else cnt=0;
ans+=cnt;//加和答案
dp[i][d]+=dp[j][d]+1;//转移方程
}
}
return ans;
}
};时间复杂度为$O(n^2)$.
516、最长回文子序列
原题链接：”https://leetcode-cn.com/problems/longest-palindromic-subsequence/"
序列dp
类似上面那道等差子序列，都是处理具有某种性质的子序列。
状态描述：dp[i][j]表示在区间[i,j]中最长回文子序列的长度，题目求的就是dp[0][n-1] （n为字符串长度,i < j）
推导过程：设字符串为s，由于所有的单个字符都为回文串，所以所有的dp[i][i]都为1，而在[i,j]区间中对s[i]和s[j]分两种情况讨论:
- 当s[i]==s[j]，那么直接将这两个字符加入[i+1,j-1]的最长回文串中即可，即转移方程为 $dp[i][j]=dp[i+1][j-1]+2$;
- 当s[i]!=s[j]，那么其并不能改变目前的最长回文串，dp[i][j]等于比[i,j]小一点点的区间里的dp值，即转移方程为 $dp[i][j]=max(dp[i+1][j],dp[i][j-1])$;
$$
dp[i][j]=\left\lbrace
\begin{array}{llc}
1 & i==j \\
dp[i+1][j-1]+2 & s[i]==s[j] \\
max(dp[i+1][j],dp[i][j-1]) & s[i]!=s[j]
\end{array}
\right.
$$
解题中需注意计算顺序，我下面写的题解是i从后往前递推，对于每个i,都让j从i+1开始往后递推，这样实质上保证了在计算dp[i][j]时，dp[i+1][j-1],dp[i][j-1],dp[i+1][j]都已经计算好了。（虽然我也写了从前往后递推的版本）
下面是代码实现
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n=s.length();
vector<vector<int> >dp(n,vector<int>(n));//相当于二维数组
for(int i=n-1;i>=0;i--){
dp[i][i]=1;//单个字符都为回文
for(int j=i+1;j<n;j++){//分类讨论
if(s[i]==s[j])dp[i][j]=dp[i+1][j-1]+2;
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
};时间复杂度为$O(n^2)$.
