首页 > 其他分享 >力扣 | 一维简单线性dp | 2140. 解决智力问题、322. 零钱兑换、2466. 统计构造好字符串的方案数、91. 解码方法、983. 最低票价、790. 多米诺和托米诺平铺

力扣 | 一维简单线性dp | 2140. 解决智力问题、322. 零钱兑换、2466. 统计构造好字符串的方案数、91. 解码方法、983. 最低票价、790. 多米诺和托米诺平铺

时间:2024-08-16 09:56:40浏览次数:13  
标签:int 983 sum 多米诺 vector questions 托米 dp mod

文章目录

需要特别注意的题目有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=3i​dp[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

相关文章

  • panic: 8e85653db463fe36 state.commit 942043166 is out of range [939698375, 93970
    根据您提供的日志信息,看起来您的etcd服务遇到了一个panic错误,具体是因为state.commit的索引值942043166超出了预期的范围[939698375,939700076]。这种情况可能是由于etcd集群中的数据不一致导致的。首先,您可以尝试查看etcd集群的状态,确认所有成员是否都在正......
  • 洛谷-P9830 题解
    思路分析分析样例:见红线,长宽各为2,存在格点;黄线长2宽3,没有格点。考虑延长黄线使得长4宽6,发现有格点。思考格点,如果长和宽都可以被分成\(p\timesl\)的格式,则存在格点。那么,就能想出:推论1:对于\((0\,\0)\)和\((x\,\y)\)之间没有格点,当且仅当\(\gcd(x\,......
  • ESP32 使用MAX98357 播放MP3
    使用ESP32和MAX98357音频放大器芯片来播放音乐,效果令人惊叹! 【ESP32开发指南】   首先使用ESP32板和MAX98357芯片进行了简单的接线,下载了ArduinoI2S的库,然后用ArduinoIDE并编写了一些简单的代码来实现音乐播放。当我们启动程序并播放这首歌时,我们听到了一个令人惊叹的......
  • Luogu P1983 车站分级 题解 [ 绿 ] [ 拓扑排序 ] [ 图论建模 ] [ 虚点 ]
    车站分级:很好的拓扑排序题,细节有点多。图论建模首先观察对于一条线路,我们可以从中直接得到什么信息:假设这条线路的开头为\(st\),结尾为\(ed\),那么在\([st,ed]\)的车站中,没有被选入线路的点一定比选入线路的点的级数至少少\(1\)。对于这一点条件,我们就可以建模了。......
  • 51nod-3983走方格
    https://class.51nod.com/Html/Textbook/Problem.html#problemId=3983&textbookChapterId=724https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337移动与时间段有关,如果按照时间段划分状态那么每一段内只有一条线性的转移。需要一行一行或......
  • CodeForces 1983A Array Divisibility
    题目链接:CodeForces1983A【ArrayDivisibility】思路    按规律可得,当a[i]=i时满足题目要求。代码#include<functional>#include<iostream>#include<algorithm>#include<queue>#include<stdio.h>#include<string>#include<cstring......
  • CodeForces 1983B Corner Twist
    题目链接:CodeForces1983B【CornerTwist】思路    可以发现操作一次,被操作位置的对应每一横行和每一纵行的加减数都是3,所以可以根据网格a和b的横纵状态确定是否通过操作使得网格a到达网格b。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglo......
  • CF1983E I Love Balls
    题意\(n\)个小球,有\(k\)个特殊小球,两个人轮流随机拿,每个小球有权值,如果拿到特殊球就再拿一个,问两个人的期望得分。题解关键1如果没有特殊小球,那么每个球是等价的,计算期望的时候可以直接用平均值作为一个小球的权值,把每个小球的权值都看成平均值关键2把拿取操作看成一个序......
  • 每日一题- CF1983F
    从未每日的每日一题E>F但是没时间了#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintt,n,a[100005],p[100005];inttr[3200005][2],id[3200005],cnt;llk;voidinit(){ for(inti=1;i<=cnt;i++)tr[i][0]=tr[i][1]=0,id[i]=0; cnt=1;}intcalc(......
  • CF1983E I Love Balls
    Problem-E-Codeforces爱丽丝和鲍勃玩摸球游戏。有\(n\)个球,其中\(k\)个是特殊球。每个球都有其价值。他们轮流且不放回地摸球,每回合随机摸一个球并获得该球的价值。特别地,如果摸到了特殊球(且至少还有一个球)则这名玩家继续摸球。如果摸到的是普通球,则换人摸球。这样轮流......