动态规划--Kin

动态规划:

1.最大子序列和

2.LIS最长递增子序列

3.LCS最长公共子序列

4.矩阵连乘

5.数字金字塔

1.最大子序列和

#include<iostream>
using namespace std;

int maxsub(int a[],int n)       
{
	int sum=0,b=0;
	for(int i=0;i<=n;i++) 
	{
		if(b>0) b+=a[i];
  		else b=a[i];
    	if(b>sum) sum=b;
  	}
	return sum;
}

int main()
{
	int a[6]={-2,11,-4,13,-5,-2};
	cout<<maxsub(a,5)<<endl;
}

2.LIS最长递增子序列

#include<iostream>
#include<algorithm> 
#define MAX_N 1010
#define INF 10010
using namespace std;

int main()
{
	int i;
	int n;
	cin>>n;
	int a[1010];
	
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	int dp[MAX_N];
	fill(dp,dp+n,INF);
	for(i=0;i<n;i++)
	{
		*lower_bound(dp,dp+n,a[i])=a[i];
	}
	cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
} 

3.LCS最长公共子序列

#include<cstring>
#include<iostream>    
#define MAXV 1000  
using namespace std; 
int dp[MAXV][MAXV];  
char s1[MAXV],s2[MAXV];  
  
bool issame(int a,int b)
{  
    return a==b?1:0;  
}  
  
int max(int a,int b,int c)
{  
    if(a>=b&&a>=c) return a;  
    if(b>=a&&b>=c) return b;  
    return c;  
}  
  
int main()
{  
    int len1,len2,i,j;    
    while(cin>>s1>>s2)
	{  
        memset(dp,0,sizeof(dp));  
        len1=strlen(s1);  
        len2=strlen(s2);  
        for(i=1;i<=len1;i++)
		{  
  			for(j=1;j<=len2;j++)
  			{  
                dp[i][j]=max(dp[i-1][j-1]+issame(s1[i-1],s2[j-1]),dp[i-1][j],dp[i][j-1]);  
            }  
        }  
		cout<<dp[len1][len2]<<endl;  
    }  
}  

4.矩阵连乘,最少的乘法次数

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[maxn][maxn],a[maxn]; 

int main()
{
    int n;
    cin>>n;
    int i,j,k,len;
    memset(dp,0,sizeof(dp)); 
    //len是设置步长,也就是j减i的值 
    for(i=0;i<n;i++) cin>>a[i];
    for(i=0;i<n-2;i++) dp[i][i+2]=a[i]*a[i+1]*a[i+2];
    //如果只有三个数就直接乘起来 
    for(len=3;len<n;len++)
    {
        for(i=0;i+len<n;i++)
        {	
			j=i+len;
            for(k=i+1;k<j;k++)
			{
				if(dp[i][j]==0) dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j];
			 	else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
            }
        }
    }
    cout<<dp[0][n-1]<<endl;
}

5.数字金字塔

include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int triangle[110][110],dp[110][110];

int main()
{
	int N;
	cin>>N;
	memset(dp,0,sizeof(dp));
	memset(triangle,0,sizeof(triangle));
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>triangle[i][j];
		}
	}
	for(int i=1;i<=N;i++)
	{
		dp[N][i]=triangle[N][i];
	}
	for(int i=N-1;i>=1;i--)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=max(dp[i+1][j]+triangle[i][j],dp[i+1][j+1]+triangle[i][j]);
		}
	}
	cout<<dp[1][1]<<endl;
}

 树形DP

1.求解树的重心

2.求解删除树的重心后的最大子树

3.父节点和子节点不能同时选择的最大数值解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3717 [AHOI2017初中组]cover

题目背景 以下为不影响题意的简化版题目。 题目描述 一个n*n的网格图上有m个探测器,每个探测器有个探测半径r,问这n*n个点中有多少个点能被探测到。 输入输出...

34870
来自专栏算法修养

单调队列,单调栈总结

最近几天接触了单调队列,还接触了单调栈,就总结一下。 其实单调队列,和单调栈都是差不多的数据类型,顾名思义就是在栈和队列上加上单调,单调递增或者单调递减。当...

61680
来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

256100
来自专栏desperate633

LeetCode 149. Max Points on a Line分析代码

将x,y的差值求最大公约数,约到最简洁的形式,然后存入map中,对每个点这样操作,如果最后x,y最后相等,那么就说明两个点具有相同的斜率,在一条直线上。同时不要...

10830
来自专栏chenjx85的技术专栏

leetcode-77-组合

vector<vector<int>> combine(int n, int k) 

17710
来自专栏决胜机器学习

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(五)——数组的压缩与转置 (原创内容,转载请注明来源,谢谢) 1、数组可以看作是多个线性表组成的数据结构,二维数组可以有两种存储方式:一种是以行...

422110
来自专栏chenjx85的技术专栏

leetcode-812-Largest Triangle Area

39190
来自专栏抠抠空间

python常见模块之random模块

python常见模块之random模块 import random print(random.random()) #随机产生一个0-1之间的小数 p...

318100
来自专栏Bingo的深度学习杂货店

Q152 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) wh...

43370
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

602140

扫码关注云+社区

领取腾讯云代金券