赫he

分类

题解(3)

/ 注册

全部文章（共55篇）

c++题解 | #买卖股票的最好时机(三)#

只能交易两次，还是从状态出发 dp[i][0]：第i天第一次持有 dp[i][1]: 第i天第一次未持有/卖出 dp[i][2]：第i天第二次持有 dp[i][3]：第i天第二次未持有/卖出状态转移： dp[i][0] = max(dp[i-1][0]"维持状态，和前一天一样处于第一次持...

2023-07-19

0 370

题解 | #买卖股票的最好时机(二)#

动态规划 dp[N][2]: dp[i][0]表示第i天不持有股票的最大收益，同理，dp[i][1] 表示第i天持有股票的最大收益。分析： dp[i][0]，第i天不持有股票（卖出股票），那这个状态可以来自两方面：1）来自dp[i-1][0]，前一天不持有股票，今天也不持有股票，最大收益不会变化；...

2023-07-17

3 495

题解 | #买卖股票的最好时机(一)#

用lastMin记录遍历到的i之前的出现的最小值1.当 p[i]<=lastMin，说明p[1~i]上的最大收益和p[1~i-1]上一样， f[i] = f[i-1]2.当p[i]>lastMin，说明有可能产生更大的收益，f[i] = max(f[i-1], p[i]-lastMin)...

2023-07-16

0 365

题解 | #过河#

如果不考虑L的范围，就是一道简单的dp题。f[i]表示走到位置i，踩到的石头个数的最小值，则f[i]=min(f[i], f[j] + flag[i])，其中flag[i]表示位置i是否是石子，j在[i-s, i-t]之间。当L很大时，但是石子个数很少最多只有100个，所以存在两个石子之间有很大的空...

2023-07-15

2 355

题解 | #跳跃游戏(三)#

「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。 #include <cstdio> #include <iostream> using namespace std; const int N = 1e5 + 10; int nums[N...

2023-07-14

0 341

题解 | #跳跃游戏(二)#

如果最大分数存在，最后一个数一定在里面初始化pos为n-1，不断向前遍历，看遍历到的位置i能否跳到pos，能说明从 i 最终可以跳到最后。如果i遍历过了0，而pos还未更新到0，说明数组不能跳到最后。举个例子：[1,2,3,0,0,1,4]，n=7。初始pos = 6 -> i=5，nums[...

2023-07-14

0 369

题解 | #跳跃游戏(一)#

记录最远可以到达的地方，在遍历每个nums时，更新最远的距离 #include <iostream> using namespace std; const int N = 2e5+10; int a[N]; int n; int main() { scanf("%d&q...

2023-07-13

0 327

题解 | #删除相邻数字的最大分数#

选中a_i，删除数组中每一个a_i+1和a_i-1的数。可以遍历1到10000中的每一个数字，出现在给定的数组中就统计次数，因为最后也是需要输出得分的。这样就是对数组counts进行动态规划转移方程数i 不选，它可以来自自身减一的数的两种状态的最大值dp[i][0] = max(dp[i-1][0]...

2023-07-12

1 646

题解 | #打家劫舍(二)#

环形的家不能同时偷第一个和最后一个。这里家的编号是从1到n。1 不偷第一个家：遍历到第i个家时，有两种情况，偷或者不偷，取二者的最大值。i的遍历范围：[3,n]，给定初值: dp1[1]=0, dp[2] = a[2]dp1[i] = max(dp[i-2]+a[i], dp[i-1])2 偷第一个...

2023-07-12

0 389

题解 | #最长回文子序列#

dp[i][j]表示字符串s的下标范围[i,j]内的最长回文子序列的长度，假设字符串s的长度为n，当时，才满足dp[i][j]>0，否则dp[i][j]=0。初始化：由于任何长度为1的子序列都是回文子序列，所以对于任意的，都有dp[i][i]=1状态转移：当i<j时，计算dp[i][j]...

2023-07-10

0 253