静寂旮旯

分类

题解(43)

/ 注册

全部文章（共46篇）

题解 | #最长上升子序列(一)#

解题思路1：首先搞清楚几个问题，到结尾点的最长上升子串应该思考成为，不是以结尾下表i结尾的子串。但是需要知道以i结尾的子串的长度。最终只要取出其中以某个点为结尾的最大长度子串就是要求的答案。递归的思维方式来解决此题，求以最后结尾点i为结束的子串长度dp[i]dp[i]dp[i]只要比较节点0～...

C++ 动态规划

2022-04-14

0 339

题解 | #[NOIP2002 普及组] 过河卒#

解题思路：利用二维数组dp 卒子只能两个方向走，一个是向右，一个是向下。可得状态方程dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]dp[i][j]=dp[i−1][j]+dp[i][j−1]。在处理马点的时候，应...

C++ 动态规划

2022-04-13

7 438

题解 | #矩阵的最小路径和#

解题思路：到达出口只能从出口左边或者上边来，这样就很容易写出递归式,并且进行记忆化搜索。也可以使用状态方程dp[i][j]=min(dp[i−1][j],dp[i][j−1])+v[i][j]dp[i][j] = min(dp[i-1][j], dp[i][j-1])+v[i][j]dp[i][...

C++ 动态规划

2022-04-11

2 347

题解 | #最大子矩阵#

关于暴力的解题思路没什么可说的，无非是搜索模式的不同。此题应该属于线性dp的一种变化，对于一位数组的连续子数组最大和的状态表达式是dp[i]=max(dp[i−1]+v[i],v[i])dp[i] = max(dp[i-1]+v[i],v[i])dp[i]=max(dp[i−1]+v[i],v[...

C++ 动态规划

2022-04-11

5 360

题解 | #环形数组的连续子数组最大和#

解题思路1：看似明显的线性dp 但是对于每一个点作为起点做dp无疑是暴力解法。时间复杂度在O(N2)O(N^2)O(N2),结果可想而知超时 #include<bits/stdc++.h>//超时的代码 using namespace std; int solve(int n, v...

C++ 动态规划

2022-04-10

19 689

题解 | #乘积为正数的最长连续子数组#

解题思路1：用0分割数组记录每一段的第一个负号和最后一个负号，以及负号的个数对于每一段，如果负号的个数为偶数则此整段就是长度如果负号的个数为奇数，则比较该段开始到第一个负号的长度a和最后一个负号到结尾的长度b。总长度-min（a，b）就是该段的长度比较每段长度取最大值即可。 #incl...

C++ 动态规划

2022-04-10

0 397