静寂旮旯

题解

/ 注册

全部文章 / 题解（共43篇）

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

解题思路：用dp记录收益之和，对于价格贪心只要当天价格比前一天高那么做一次交易，dp加上收益一直到结束，输出，时间复杂度O(n)O(n)O(n),空间复杂度O(1)O(1)O(1)。 #include<bits/stdc++.h> using namespace std; int...

C++ 动态规划

2022-05-02

0 350

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

解题思路：数据量为1E5，那么使用O(n2)O(n^2)O(n2)的解法大概率会超时。分析问题，只要在股票每一天价格中记录最大正向价格差即可，即读入一个价格，如果当前价格比前一天的价格还低则以当前价格暂时做为买入价格，否则记录正向价格差，那么在次过程中的使用一个变量dp记录最大正向价格差即可。...

C++ 动态规划

2022-05-02

2 318

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

解题思路：超时坑点，从前往后推，简单明了的思路，dp[i]表示走到i点的最小步数，那么dp[0] = 1;对于i>0的点，有j0:i−1,j+v[j]>=i,dp[i]=min(dp[j0]:dp[ji−1]+1)j_{0:i-1},j+v[j]>=i,dp[i] = min(...

C++ 动态规划

2022-04-29

1 338

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

解题思路：不能递归了，递归栈真的会炸。递推进行，不能常规地从左往右推，而应该从右往左推，即答案位于dp[0]。先讨论一般情况，dp[i]表达的是此位置能到达n-1位置所能得到的最大分数。那么对于任一位置i有：dp[i]=max(dpi+1:n−1+v[i])dp[i] = max(dp_{i...

C++ 动态规划

2022-04-29

0 326

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

解题思路：普通的dp会超时，在输入过程中直接执行dp，令mx_idx表示当前i下所能到达的最远下标，每次输入取所能到达下标的最大值，假如能到达下标n-1则返回true，但如果在此过程中出现下标i的v为0，而该下标恰好是mx_idx所能达到的最远下标，则不能再继续往下走，可以中断，并返回false...

C++ 动态规划

2022-04-28

0 473

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

解题思路：做之前处理下数据，数据的大小是1E4，开一个数组建立一个桶v，对于输入的每一个数据，以数据值做下标，对应的桶数值++即可，再讲输入的数丢入一个set中，习惯操作vector，又将数丢到了v2中，操作的时候只要在这个set中的每一个数依次向后动态规划即可。从左往右考虑，在i行进的过程中...

C++ 动态规划

2022-04-28

1 596

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

解题思路：取最大不相邻数之和的变种，原问题可以看作前n-1个数的最大不相邻数之和，和后n-1个数的最大不相邻之和，取两者的最大值即可。 #include<bits/stdc++.h> using namespace std; long long solve(vector<in...

C++ 动态规划

2022-04-28

2 410

题解 | #不相邻取数#

解题思路：此题必须空间优化，一般情况：dp[i]=max(dp[i−2]+v[i],dp[i−1])dp[i] = max(dp[i-2]+v[i],dp[i-1])dp[i]=max(dp[i−2]+v[i],dp[i−1]) #include<bits/stdc++.h> us...

C++ 动态规划

2022-04-28

0 296

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

解题思路：建立模型为最长公共子序列。则只要求出s和sr（倒序）的最长公共子序列即可。一般情况：dp[i][j]=max(dp[i−1][j−1]+(int)(s[i]==sr[j]),max(dp[i−1][j],dp[i][j−1]))dp[i][j] = max(dp[i-1][j-1]+...

C++ 动态规划

2022-04-28

0 320

题解 | #正则表达式匹配#

解题思路：题是写出来了，但是感觉像假做。可能是测试数据不行。有时写递归感觉心里没底。先递归解决问题，再记忆化，就成了dp，估计后面还有优化的空间。有时候写dp，先费劲脑力把递归思路想出来。管它什么套路。首先考虑一般情况。想要使得str和pattern匹配，从结尾开始，考虑我从哪里来。这里要分一...

C++ 动态规划字符串

2022-04-27

2 330