文章目录
需要特别注意的题目有2140. 解决智力问题和983. 最低票价,因为这两个题目可以启发思路,其他的题都比较普通。
一、2140. 解决智力问题
LeetCode:2140. 解决智力问题
这个题目也许像309. 买卖股票的最佳时机含冷冻期,这个股票买卖是卖出去之后又一天冷冻期,而这里像是买了今天的就会产生一个不定的冷冻期。股票买卖,我们使用的是状态机的思考,给每天定义多个状态。 而本题却不能这样做,因为冷冻期不止是一天,而是考虑各种情况买入冷冻的很多天。
我们再思考一下,这个问题好像不太好解决,因为动态规划要求没有后效性:
- 定义
dp[i]
为前i
天最高得分,bug:无法知道冷冻的信息,不好进行状态转移也就是有后效性,除非二维循环 - 定义
dp[i]
为第i
天获得分数,前i
天最高得分,bug:第i
天获得分数,那么转移至它的必然是那些不为导致其冻结的天,但是这些天并不好找,比如第一天冷冻5天,第10天它也可以进行转移,这也需要二维循环!
既然都有后效性,我们再来考虑一个问题,他是从前往后来考虑问题,那么我们是否可以从后往前考虑问题!
这样第i
天获得分数,并不影响往后的遍历!(怎么想到的,突然想到的。。下次怎么想到呢? 植入后效性->反着思考的思想)
那么我们就能直接定义了:
- 定义 d p [ i ] 为从后往前看的前 i 天获得的最高分数 定义dp[i]为从后往前看的前i天获得的最高分数 定义dp[i]为从后往前看的前i天获得的最高分数, 则有 d p [ i ] = m a x ( d p [ i + 1 ] , d p [ i + q u e s t i o n s [ i ] [ 1 ] + 1 ] + q u e s t i o n s [ i ] [ 0 ] ) 则有dp[i] = max(dp[i + 1], dp[i + questions[i][1] + 1] + questions[i][0]) 则有dp[i]=max(dp[i+1],dp[i+questions[i][1]+1]+questions[i][0])
class Solution {
public:
long long mostPoints(vector<vector<int>>& questions) {
vector<long long> dp(questions.size(), 0);//dp[i] 第i天买的最高分数
long long mx = 0;
dp[questions.size() - 1] = questions.back()[0];
for(int i = (int) questions.size() - 2; i >= 0; -- i){
long long pre = i + questions[i][1] + 1 < questions.size() ? dp[i + questions[i][1] + 1] : 0;
dp[i] = max(dp[i + 1], pre + questions[i][0]);
}
return dp[0];
}
};
二、322. 零钱兑换
LeetCode:322. 零钱兑换
本题很显然是一个完全背包问题,每个硬币能使用无限次。
我们定义
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示 在能使用coins[i]
时,总金额达到j
使用最少的硬币个数。
金额从前往后遍历:
dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i]] + 1)
初始化:
当金额为0
的时候,只有一种组合情况,其他情况初始化为无穷大。
初始化是这个问题最难的部分,因为实际上如果了解完全背包问题,状态转移很容易写出来,初始化需要思考,由于这里是取最小值,所以我们只能定义无穷大来指明这个值目前还是不存在的,当金额为0
的时候,实际情况实际上就是组合为∅
的时候,也就是硬币个数为0
,这样我们就解决了这个问题。
空间优化:
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0x3f3f3f3f);
dp[0] = 0;
for(int i = 0; i < coins.size(); ++ i){
for(int j = coins[i]; j <= amount; ++ j){
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
}
};
完全背包问题:
我们遇到过的完全背包问题:整数拆分(518. 零钱兑换 II), 和这个题目有什么区别呢?
这两个题目都是不考虑组合顺序的,只考虑组合(之后会有组合的顺序问题,这里先不考虑)。
实际上是状态定义 和 状态转移不同,本质上是同一类dp
问题,因为我们可以枚举 可以选择的正整数 以及 枚举需要合并成的正整数,依次求出,直到求出答案。因为这里不需要考虑组合的顺序,因此我们直接进行状态转移即可。
三、2466. 统计构造好字符串的方案数
LeetCode:2466. 统计构造好字符串的方案数
定义
d
p
[
i
]
dp[i]
dp[i]表示,长度为i
的字符串可以构造的数目。、
状态转移:
dp[i] = dp[i - zero] + dp[i - one]
初始化:
dp[0] = 1
,表示当长度为0
的时候,只有一种构造方式。
其余初始化为0
即可,原因在于,不存在的构造方式,构造数目就是0
,不影响状态转移。
class Solution {
public:
int countGoodStrings(int low, int high, int zero, int one) {
vector<int> dp(high + 1, 0);//dp[i]表示
dp[0] = 1;
int ans = 0;
int mod = 1e9 + 7;
for(int i = 1; i <= high; ++ i){
if(i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % mod;
if(i - zero >= 0) dp[i] = (dp[i - zero] + dp[i]) % mod;
if(i >= low) ans = (ans + dp[i]) % mod;
}
return ans;
}
};
四、91. 解码方法
LeetCode:91. 解码方法
定义
d
p
[
i
]
dp[i]
dp[i]表示前i
个字符可以编码的数量。
状态转移:
实际上这里编码要求编码成不一样的,我们只需要保证最后一个字符不相同即可。因此对于长度为i
的最后一个字符,有两种情况,第一种是用1~9
编码,第二种是用10~26
编码,我们来考虑即可。
在满足条件下:
dp[i] = dp[i - 1] + dp[i - 2]
初始化:
空串编码方式为1
,即dp[0] = 1
class Solution {
public:
int numDecodings(string s) {
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for(int i = 1; i <= s.size(); ++ i){
if(s[i - 1] != '0') dp[i] += dp[i - 1];//任何时候包含前导0 答案都是0
if(i >= 2){
int codeNum = stoi(s.substr(i - 2, 2));
if(codeNum >= 10 && codeNum <=26)
dp[i] += dp[i - 2];
}
}
return dp[s.size()];
}
};
由于dp
只考虑前两个,可以使用滚动数组,优化空间。
并且一般情况下,不要使用substr
,这个方法是
O
(
m
)
O(m)
O(m)的。(处理的字符串部分长度)
五、983. 最低票价
LeetCode:983. 最低票价
如果不标明是一个动态规划题,你能想到用动态规划吗?
可能一开始想用贪心,因为无论如何只有365
天,在每个时间段里贪,但时间段是无限重叠和交叉的,你无法区分。暴力也不是办法,那就看看动态规划吧!
这个通行证像极了冷冻期,也就是说在第i
天买了通行证,那么后面的日期多会收到影响,我们可以考虑从后往前看,从后往前看买一张通行证只会影响后面的日期,不会影响前面的。就没有后效性了。
我们直接 O ( n 2 ) O(n^2) O(n2)好像也没事,毕竟。。毕竟 n = 365 n = 365 n=365, 好吧,从后往前确实不错,不过我们还是得找到对应的时间才能状态转移。甚至还能使用二分降到 O ( n l o g n ) O(nlogn) O(nlogn)
那就,定义状态
d
p
[
i
]
dp[i]
dp[i]表示完成前i
个天所需的最小消费
状态转移:
我们保证每个通行证发挥出最大的功效,则有
d
p
[
i
]
=
d
p
[
i
−
k
]
+
c
o
s
t
s
[
m
]
dp[i] = dp[i - k] + costs[m]
dp[i]=dp[i−k]+costs[m],其中dp[i-k]
是通行证m
刚好不能涵盖的那个天。
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
vector<int> dp(days.size() + 1, 0x3f3f3f3f);
dp[0] = 0;//花费0元
for(int i = 1; i < dp.size(); ++ i){
dp[i] = min(dp[i - 1] + costs[0], dp[i]);//一天的单独考虑了
int day1 = days[i - 1] - 6;
int day2 = days[i - 1] - 29;
auto it = lower_bound(days.begin(), days.end(), day1);//寻找7天的极限
int pos = it - days.begin();
dp[i] = min(dp[pos] + costs[1], dp[i]);
it = lower_bound(days.begin(), days.end(), day2);
pos = it - days.begin();
dp[i] = min(dp[pos] + costs[2], dp[i]);
}
return dp[days.size()];
}
};
官解:
官解实际上是从后往前消除后效性的两个思路:
(1)不管有多少天,都考虑365
天,然后对于不在里面的就不买,相当于花的钱和后一天的钱一模一样。(实际上很多题都有这样的思路,就是把没有的补充,只是不做处理,保留下来)
(2)往后遍历,找到所需的天,由于通行证最多30天,因此我们最多只需要往后找30天即可。
六、790. 多米诺和托米诺平铺
LeetCode:790. 多米诺和托米诺平铺
这实际上也是一个简单的动态规划,我们只需要找到基础拼凑方法即可。
实际上基础拼凑法就四种,一种是2×1
竖着,一种是两块2×1
横着,一种是L
型凑成的两种如图种下面两种。
还有一种平凑法可以无限延长,这个长度涵盖了大于等于4的所有情况,并且有上下翻转两种,如下:
因此,定义
d
p
[
i
]
dp[i]
dp[i]表示长度为n
能够普成的数量,则状态转移方程:
d
p
[
i
]
=
d
p
[
i
−
1
]
+
d
p
[
i
−
2
]
+
∑
k
=
3
i
d
p
[
i
−
k
]
∗
2
dp[i] = dp[i - 1] + dp[i - 2] + \sum_{k=3}^{i}{dp[i - k] * 2}
dp[i]=dp[i−1]+dp[i−2]+∑k=3idp[i−k]∗2,所以我们引入前缀和即可。
class Solution {
public:
int numTilings(int n) {
vector<int> dp(n + 1, 0);
vector<long long> sum(n + 1, 0);
int mod = 1e9 + 7;
dp[0] = sum[0] = 1;
for(int i = 1; i <= n; ++ i){
dp[i] += dp[i - 1];
if(i >= 2) dp[i] = (dp[i] + dp[i - 2]) % mod;
if(i >= 3) dp[i] = (dp[i] + sum[i - 3] * 2) % mod;
sum[i] = (dp[i] + sum[i - 1]) % mod;
}
return dp[n];
}
};
当然可以使用滚动数组来进行空间优化。
不过我们可以学习一下,对sum
进行优化,实际上我们一直需要使用的是sum[i - 3]
,我们只需要维护sum[i - 3]
即可,i
增大,实际上i - 3
也增大,加上对应的那个即可。
class Solution {
public:
int numTilings(int n) {
vector<int> dp(n + 1, 0);
long long sum;
int mod = 1e9 + 7;
dp[0] = sum = 1;
for(int i = 1; i <= n; ++ i){
dp[i] += dp[i - 1];
if(i >= 2) dp[i] = (dp[i] + dp[i - 2]) % mod;
if(i >= 3) dp[i] = (dp[i] + sum * 2) % mod, sum = (sum + dp[i - 2]) % mod;
}
return dp[n];
}
};
标签:int,983,sum,多米诺,vector,questions,托米,dp,mod
From: https://blog.csdn.net/m0_63997099/article/details/141197618