算法-子串子序列最值问题

leetcode 32.最长有效括号

左神 中级提升班 3-2

class Solution {     public int f(String s) {         //1         char[] chs = s.toCharArray();         int n = s.length();         //表示以i结尾的最长有效子串         int[] dp = new int[n];         dp[0] = 0;         //2         for (int i = 1; i < n; i++) {             //analyse chs[i]             if (chs[i] == '(') {                 dp[i] = 0;             } else {                 if (i - dp[i - 1] - 1 >= 0 && chs[i - dp[i - 1] - 1] == '(') {                     dp[i] = dp[i - 1] + ((i - dp[i - 1] - 2 >= 0) ? dp[i - dp[i - 1] - 2] : 0) + 2;                 }             }         }         int ans = -1;         for (int i = 0; i < n; i++) {             ans = Math.max(ans, dp[i]);         }         return ans;     } }

 

推荐这些文章:

516. 最长回文子序列

动态规划
class Solution {
public int longestPalindromeSubseq(String s) {

/**
* 类似于《647. 回文子串》
* dp[i][j]定义为区间为[i, j]内最长的回文子串长度
* 初始化每个字符就是一个回文串,即每个dp[i][i] == 1
*/
int[][] dp = new int[s.length()][s.length()];

for (int i = s.length() - 1...

leetcode 309. 最佳买卖股票时机含冷冻期

class Solution {
public int maxProfit(int[] prices) {
int len=prices.length;
// 0: no stock; 1: hold stock; 2: no stock & in frozen stage
int[] dp=new int[3];
dp[1]=-prices[0];
for(int i=1;i<len;i++){
int d0=Math.max(dp[0],dp[2]);
...

最长不下降子序列(LIS)问题

再解问题前,我们先看题目:

 我们模拟一下程序的运行过程。可以看到a数组中的 -1 对应dp数组的是1,是因为在a数组中-1的前面没有比-1小的数,而a数组中的3对应的dp数组是3,是因为在3的前面(包括它自己)有3个<=它的数(1和2)。后面的以此类推。

这个问题的状态转移方程是:

1 if(a[i]>=a[j]&&(dp[j]+1>dp[i]))//状态转移方程
2 {
3 dp[i]=dp[j]+1;//执行的操作
4 }

 
 
完整程序是这样的:

1 #include<bits/stdc++....

leetcode 188. 买卖股票的最佳时机 IV

本质和买卖股票的最佳时机3一样。
class Solution {
public int maxProfit(int k, int[] prices) {
int len=prices.length;
if(len==0||k==0) return 0;
int k2=k*2;
int[] dp=new int[k2];
for(int i=0;i<k2;i+=2){
dp[i]=-prices[0];
}
for(int i=1;i<...

动态规划DP入门问题----最大连续子序列,最长不下降子序列(可以不连续),最长公共子序列

一、最大连续子序列
1.题目叙述

对于一个数字序列A1A2A3...An,求出连续子序列的最大和,如对于序列-2,11,-4,13,-5,-2,其中的最大序列和是11+(-4)+13=20 

2.动态规划解法
将问题拆分成子问题,即dp[i]表示以A[i]为结尾的子序列的最大和,最后对于这些dp数组找出最大值即可,状态转移方程为:

dp[i] = max{ dp[i-1] + A[i] }  状态dp[i]表示,当前以A【i】结尾的子序列的最大和

3.方法一是经典算法,方法二是根据状态方程优化而来。

#include<iostream>
#inclu...

木棍加工——线性dp、dilworth定理、最长上升子序列

P1233 木棍加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
读题可知我们要求的是将所有木棍分割成长度与宽度都是不上升子序列的序列个数。
既然是不上升子序列,那么我们就结构体排序一下。

1 bool cmp(const node&s1,const node&s2)
2 {
3 if(s1.l==s2.l)return s1.w>s2.w;
4 return s1.l>s2.l;
5 }

 
根据dilworth定理:
  一个序列要最少分割为多少个不上升子序列的个数等于该序列最长上升子序列的长度。
  注意:...

【完虐算法】「字符串-最长公共子序列」全面总结

你好!我是Johngo!
LeetCode专题「字符串」现在准备到了 5 期内容来啦。
本来想要把「最长公共子序列」和「最长上升子序列」一起和大家把思路分享一下,都属于可以使用动态规划的思想进行解决。但貌似还是两块内容。
所以,今天先把「最长公共子序列」分享出来和大家聊聊。
后面再出一期把「最长上升子序列」详细的分享,后面这一期内容估计会比较多。
题外话,上一期的抽书活动还没有结束,感兴趣的可以继续参与哈!【 https://mp.weixin.qq.com/s/V9srFVVrDxVRW8XYNK8pLg 】
说在前面
言归正传,这一期来说说字符串的第五块内容 「字符串 - 最长公共子序列...

leetcode 376. 摆动序列

解法1:贪心。
除去中间单调的节点即可。
class Solution {
public int wiggleMaxLength(int[] nums) {
int n=nums.length;
int ans=1;
int prevSub=0;
for(int i=1;i<n;i++){
int sub=nums[i]-nums[i-1];
if((sub<0&&prevSub>=0)||(sub>0&&prevS...

剑指 Offer 47. 礼物的最大价值

剑指 Offer 47. 礼物的最大价值

这里有一个好处在于所有值都是正的,所以处理起来不用像子数组一样处理和为负要重新选择,但是这里也是比较简单的。
可以用dp[i][j]记录我们走到[i][j]位置时所能获得的礼物最大价值,那么很显然,我们到达[i][j]位置有2种方式,从[i-1][j]即从上往下或是从[i][j-1]即从左往右到达,那么我们选择这两种方式到达的最大价值的那条,故而dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1])。同时一直维护ans即可。
class Solution {
public i...

最长公共子序列(模板题)

1.今天学了一手最长上升子序(模板题)
 
贴一下代码吧(输出最大路径值与输出路径

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int p[1010];//p数组是记录路径下标
int f[1010];
int n;
void print(int i){//这里是输出路径,递推式,sum值逐渐递减
if(p[i]) print(p[i]);
printf("%d ",a[i]);
}
int main(){
cin>>n;
for(int i=1;i&l...

文章标题:算法-子串子序列最值问题
文章链接:https://www.dianjilingqu.com/1526.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>