Java教程
算法——动态规划算法
本文主要是介绍算法——动态规划算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
文章目录
- 一：最长公共子序列
- 1.问题描述
- 2.程序代码
- 二：矩阵连乘
- 1.问题描述
- 2.程序代码
- 三：最大子段和
- 1.问题描述
- 2.思路分析
- 3.程序代码
- 四：最大k乘积问题
- 1.问题描述
- 2.程序代码
一：最长公共子序列
1.问题描述
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
输入：
BADFDACBRKDS JHBAFDACGK
输出：
B A F D A C K
2.程序代码
package Test2;
//最长公共子序列 SubString.java
import java.util.Scanner;
public class SubString {
static void LCSLength (String x,String y,int b[][])
{
int m,n,i,j;
m=x.length()-1;
n=y.length()-1;
int [][]c=new int[m+1][n+1];
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j<= n; j++)
{
if (x.charAt(i)==y.charAt(j))//(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if (c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
static void LCS(int i,int j, String x,int b[][])
{
if (i ==0 || j==0) return;
if (b[i][j]== 1)
{
LCS(i-1,j-1,x,b);
System.out.print(x.charAt(i)+" ");
}
else if (b[i][j]== 2)
LCS(i-1,j,x,b);
else
LCS(i,j-1,x,b);
}
public static void main(String[] args) {
String x,y;
Scanner scan=new Scanner(System.in);
System.out.println("input two strings:");
x=scan.next();
y=scan.next();
x=" "+x;
y=" "+y;
int[][] b=new int[x.length()+1][y.length()+1];
LCSLength(x,y,b);
System.out.println("The result is:");
LCS(x.length()-1, y.length()-1, x, b);
}
}
二：矩阵连乘
1.问题描述
在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。由该公式知计算C=AB总共需要pqr次的数乘。其标准计算公式为：
给定n个矩阵{A1,A2,…,An}。其中Ai与Ai+1是可乘的，i=1,2,…,n-1。要求计算出这n个矩阵的连乘积A1A2…An，最少的乘法次数。
递归公式：
2.程序代码
package Test2;
//矩阵连乘 Matrix.java
public class Matrix {
private int m[][];
private int p[];
private int s[][];
public Matrix() {
this.p =new int[]{6,39,15,20,23,2,75};
//this.p =new int[]{30,35,15,5,10,20,25};
//this.p =new int[]{15,5,105,55,100,250,25};
this.m = new int [p.length+1][p.length+1];
this.s = new int [p.length+1][p.length+1];
}
public void matrixChain( )
{ int n= p.length-1;
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++)
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t; s[i][j] = k;}
}
}
}
public void traceback(int i,int j)
{ if(i==j)
System.out.print("A"+i);
else if(i+1==j)
System.out.print(" (A"+i+" * "+" A"+j+") ");
else{
System.out.print(" (");
traceback(i, s[i][j]);
traceback(s[i][j]+1,j);
System.out.print(") ");
}
}
// 备忘录方法
public int memoizedmatrixChain( )
{ int n= p.length-1;
for (int i=1;i<=n;i++)
for(int j=1; j<=n; j++)
m[i][j]=0;
return lookupChain(1,n);
}
private int lookupChain( int i, int j)
{
if (m[i][j] > 0) return m[i][j];
if (i == j) return 0;
int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t=lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
if (t < u)
{ u = t; s[i][j] = k; }
}
m[i][j] = u;
return u;
}
public static void main(String[] args) {
Matrix m=new Matrix();
m.matrixChain();
System.out.println("动态规划方法，乘法的最优次序：");
m.traceback(1, m.p.length-1);
Matrix m1=new Matrix();
m1.memoizedmatrixChain();
System.out.println("");
System.out.println("备忘录方法，乘法的最优次序：");
m1.traceback(1, m.p.length-1);
}
}
三：最大子段和
1.问题描述
给定由n个整数（可能有负整数）组成的序列（a1,a2,…,an），最大子段和问题要求该序列形如 的最大值（1<=i<=j<=n），当序列中所有整数均为负整数时，其最大子段和为0。
2.思路分析
求一个序列中截取一段连续的序列，要求截取的序列的和为最大值。
举例：
如序列为（-5,8,12,-6,8,-14）的最大连续的序列为（8,12,-6,8）其和为22
如序列为（-5,8,12,-6,8,-14,-15,5,20）的最大连续的序列为（5,20）其和为25
如序列为（-5,-8,-6,-14）无最大连续的序列，最大子段和为0
蛮力法 思路：找出序列的所有连续的序列，然后找出最大子段和
难点：这个区别于全排列，连续的序列是连续的（有点废话。。），所以通过两个for循环扫描即可，一个指向序列的头，一个指向序列的尾部扫秒即可。
分治法 思路：将序列S=(a 1 , a 2 , . . . , a n )划分成两个长度相同的连续序列A=(a 1 , a 2 , .
. . , a n / 2 )和连续序列B=(a n / 2 + 1 , . . . , a n )。则最大子段和有三种情况：
A中的最大子段和为S的最大子段和 B中的最大子段和为S的最大子段和 S的最大子段和为A和B中交界部分，应为∑ k = i j a k 且i
∈ ( 1 , n / 2 ) , j ∈ ( n / 2 + 1 , n )
i\in(1,n/2),j\in(n/2+1,n)i∈(1,n/2),j∈(n/2+1,n)
难点：求A和B中的交界部分的最大子段和。从n/2处分别往左右两端找出最大子段和，然后合并左右的最大子段和即为交界部分的最大子段和。
3.程序代码
package Test2;
import java.util.ArrayList;
public class suanfa3{
public static void main(String[] args) {
int[] arr = {10,-5,8,12,-6,8,-14,-15,5,20};
System.out.println("数组为：");
for (int i = 0; i < arr.length; i++) System.out.print(arr[i]+" ");
System.out.println();
System.out.println("蛮力法求解最大字段和为：");
System.out.println(maxSubseqSumByBF(arr));
System.out.println("分治法求解最大字段和为：");
System.out.println(maxSubseqSumByDC(arr,0,arr.length-1));
System.out.println("动态规划求解最大字段和为：");
System.out.println(maxSubseqSumByDP(arr));
System.out.println("自己idea求解最大子段和为：");
System.out.println(maxSubseqSumByme(arr));
}
//蛮力法
public static int maxSubseqSumByBF(int arr[]){
int length = arr.length;
int maxSum = 0; //用来记录最大值
for (int i = 0; i < length; i++) { //这个循环扫描出所有连续序列
int nowSum = 0;
for (int j = i; j < length; j++) { //这个循环扫描出所有的以i开头的连续序列
nowSum += arr[j];
if(nowSum > maxSum){
maxSum = nowSum;
}
}
}
return maxSum;
}
//分治法（递归方法求解）
public static int maxSubseqSumByDC(int arr[],int lo,int hi){
int center = lo + (hi-lo)/2;
int maxLeftSum,maxRightSum; //分别表示左右最大字段和
int borLeftSum,borRightSum; //分别表示在center左右的最大字段和
if(lo == hi){
if(arr[lo] > 0)
return arr[lo];
else
return 0;
}
maxLeftSum = maxSubseqSumByDC(arr,lo,center);
maxRightSum = maxSubseqSumByDC(arr,center+1,hi);
//求解交界部分的最大值，并与左右部分比较得出最大子段和
borLeftSum = 0;
borRightSum = 0;
int tempSum = 0;
for (int i = center; i <= hi; i++) { //往右找出最大子段和
tempSum += arr[i];
if(tempSum > borRightSum){
borRightSum = tempSum;
}
}
tempSum = 0;
for (int i = center; i >= lo; i--) { //往左找出最大子段和
tempSum += arr[i];
if(tempSum > borLeftSum){
borLeftSum = tempSum;
}
}
//比较左，右，交界处的子段和得出最大字段和
int maxSum = Math.max(maxLeftSum,maxRightSum);
maxSum = Math.max(maxSum,borLeftSum+borRightSum-arr[center]);
return maxSum;
}
//动态规划
public static int maxSubseqSumByDP(int arr[]){
int length = arr.length;
int MaxSum = 0,NowSum = 0;
for (int i = 0; i < length; i++) {
NowSum += arr[i];
if(NowSum < 0){
NowSum = 0;
}
MaxSum = Math.max(NowSum,MaxSum);
}
return MaxSum;
}
//自己的idea
public static int maxSubseqSumByme(int[] arr){
int len = arr.length;
int[] tempValue = new int[len]; //记录暂时的值
ArrayList<Integer> alist = new ArrayList<>(); //存储数据为（正,负,正,负...）或（负,正,负...）
tempValue[0] = arr[0]; //先考虑第一个，为了不越界
//找出序列中连续存在的正数总和和负数总和
for (int i = 1; i < len; i++) {
if(arr[i-1] < 0 && arr[i] < 0){
tempValue[i] = arr[i] + tempValue[i-1];
}else if(arr[i-1] > 0 && arr[i] > 0){
tempValue[i] = arr[i] + tempValue[i-1];
}else{
tempValue[i] = arr[i];
alist.add(tempValue[i-1]); //这里为什么存储的i-1需要理解一下
}
}
alist.add(tempValue[len-1]); //将最后一个存储进去
//求解最大子段和
int maxValue = alist.get(0)>0?alist.get(0):0; //先考虑第一个，为了不越界
for (int i = 1; i < alist.size(); i++) {
if(alist.get(i)>0){
maxValue = Math.max(alist.get(i),maxValue+alist.get(i-1)+alist.get(i));
}
}
return maxValue;
}
}
四：最大k乘积问题
1.问题描述
设X是一个n位十进制整数，如果将X划分为K段，则可得到K个整数，这K个整数的乘积称为X的一个K乘积。请设计算法并编程实现，对于给定的X 和K，求出X的最大K乘积。
输入：X，K，n
L
输出：X的最大K乘积。
实现提示：设f(s,t)是X从第s位开始的t位数字组成的十进制数，t(i,j)表示前 i 位数分成 j 段的最大乘积，则状态转移方程为：
t(i,j) = max{ t(k,j-1) * f(k,i-k) } (1<=k<i)
2.程序代码
package Test2;
import java.util.Scanner;
public class suanfa4 {
public static void main(String[] args){
int n, k;
int[][] m = new int[20][20];
String num = new String();
Scanner reader = new Scanner(System.in);
System.out.print("输入n的值：");
n = reader.nextInt();
System.out.print("输入k的值：");
k = reader.nextInt();
System.out.print("输入要进行分段的十进制n位整数：");
num = reader.next();
chengji.solve(num, m, n, k);
System.out.println("最大k乘积为：" + m[n][k]);
reader.close();
}
public static void solve(String num, int m[][], int n, int k){
int max, flag;
m[1][1] = num.charAt(0)-'0';
for(int i = 2; i <= n; i++)
m[i][1] = m[i-1][1] * 10 + num.charAt(i-1) - '0'; //初始化第一列
for(int j = 2; j <= k; j++){ //按列进行初始化
max = -1;
for(int i = 1; i <= n; i++){
if(j > i)
m[i][j] = 0;
else{
for(int l = j-1; l <= i-1; l++){
flag = m[l][j-1] * StrtoInt(num, l+1, i);
if(flag > max)
max = flag;
}
m[i][j] = max;
}
}
}
}
//字符串转换为整型函数
public static int StrtoInt(String str, int i, int j){
int sum = 0;
while(i <= j){
sum = sum*10 + str.charAt(i-1) - '0';
i++;
}
return sum;
}
}
这篇关于算法——动态规划算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么修改Kafka的JVM参数？-icode9专业技术文章分享12-24
-
线下车企门店如何实现线上线下融合？12-23
-
鸿蒙Next ArkTS编程规范总结12-23
-
物流团队冬至高效运转，哪款办公软件可助力风险评估？12-23
-
优化库存，提升效率：医药企业如何借助看板软件实现仓库智能化12-23
-
项目管理零负担！轻量化看板工具如何助力团队协作12-23
-
电商活动复盘，为何是团队成长的核心环节？12-23
-
鸿蒙Next ArkTS高性能编程实战12-23
-
数据驱动：电商复盘从基础到进阶！12-23
-
从数据到客户：跨境电商如何通过销售跟踪工具提升营销精准度？12-23
-
汽车4S店运营效率提升的核心工具12-23
-
ERP 系统开发案例：用 PERT 图打造高效项目管理12-23
-
初创团队必备！全面解析支持甘特图的项目管理工具与功能特点12-23
-
任务进度跟踪不再难！可视化项目协作工具精选12-23
-
看板工具为汽车销售门店协作赋能：关键方法12-23
栏目导航
