# java 动态规划策略原理及例题

2018/06/25 11:30

## 动态规划的解题核心

1. 第一步：状态的定义
2. 第二步：状态转移方程的定义

### 第二步：状态转移方程的定义

Fk=max{Fk-1+Ak,Ak}
Fk是前k项的和，Ak是第k项的值

## 例题1: 数塔取数问题

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long max = 0;
int[][] dp = new int[n][n];
dp[0][0] = in.nextInt();
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
int num = in.nextInt();
if (j == 0)
dp[i][j] = dp[i - 1][j] + num;
else
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + num;
max = Math.max(dp[i][j], max);
}
}
System.out.println(max);
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24

## 例题2:编辑距离

sitten （k->s）
sittin （e->i）
sitting （->g）

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
String aStr = in.nextLine();
String bStr = in.nextLine();
int aLen = aStr.length();
int bLen = bStr.length();
int[][] dp = new int[aLen + 1][bLen + 1];
for (int i = 0; i < aLen + 1; i++) dp[i][0] = i;
for (int i = 0; i < bLen + 1; i++) dp[0][i] = i;
for (int i = 1; i < aLen + 1; i++)
for (int j = 1; j < bLen + 1; j++)
if (aStr.charAt(i - 1) == bStr.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
System.out.println(dp[aLen][bLen]);
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23

## 例题3:矩阵取数问题

1 3 3
2 1 3
2 2 1

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] dp = new int[n + 1];
int[] readArr = new int[n + 1];
for (int i = 0; i < n; i++) {
for (int k = 1; k < n + 1; k++)
for (int j = 1; j < n + 1; j++)
dp[j] = Math.max(dp[j], dp[j - 1]) + readArr[j];
}
System.out.println(dp[n]);
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

## 例题4:背包问题

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int v = in.nextInt();
int[] dp = new int[v + 1];
int[] price = new int[n + 1];
int[] weight = new int[n + 1];
long max = 0;
for (int i = 1; i < n + 1; i++) {
weight[i] = in.nextInt();
price[i] = in.nextInt();
}
for (int i = 1; i < n + 1; i++)
for (int j = v; j > 0; j--)
if (j - weight[i] >= 0)
dp[j] = Math.max(dp[j], dp[j - weight[i]] + price[i]);
else
dp[j] = dp[j];
for (int i = 0; i < v + 1; i++)
max = max > dp[i] ? max : dp[i];
System.out.println(max);
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26

## 例题5:最长递增子序列

(递增子序列是指，子序列的元素是递增的）

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] L = new int[n];
for (int j = 0; j < n; j++)
L[j] = in.nextInt();

double[] B = new double[n + 1];
B[0] = Integer.MIN_VALUE;
B[1] = L[0];
int Len = 1;
int p, r, m;
for (int i = 1; i < n; i++) {
p = 0;
r = Len;
while (p <= r) {
m = (p + r) / 2;
if (B[m] < L[i])
p = m + 1;
else
r = m - 1;
}
B[p] = L[i];
if (p > Len)
Len++;
}
System.out.println(Len);
}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35

## 例题6:最大子段和

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
long max = 0, subMax = 0;
for (int i = 0; i < n; i++) {
subMax += in.nextInt();
if (max < subMax)
max = subMax;
if (subMax < 0)
subMax = 0;
}
System.out.println(max);
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

## 例题7:最长公共子序列Lcs

abcicba
abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String aStr = in.nextLine();
String bStr = in.nextLine();
int aLen = aStr.length();
int bLen = bStr.length();
int[][] dp = new int[aLen + 1][bLen + 1];
for (int i = 1; i < aLen + 1; i++)
for (int j = 1; j < bLen + 1; j++)
if (dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)
&& dp[i - 1][j] == dp[i - 1][j - 1])
dp[i][j] = dp[i - 1][j] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
int max = dp[aLen][bLen];
StringBuilder sb = new StringBuilder();
while (max > 0) {
if (dp[aLen - 1][bLen] == dp[aLen][bLen - 1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]) {
sb.append(aStr.charAt(aLen - 1));
max--;
aLen--;
bLen--;
} else {
if (dp[aLen][bLen - 1] == dp[aLen][bLen])
bLen--;
else
aLen--;
}
}

System.out.println(sb.reverse().toString());
}
}
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37

## 例题8:正整数分组

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);
int n = in.nextInt();
long sum = 0, max = 0;
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
sum += nums[i];
}
int[] dp = new int[(int) (sum / 2 + 1)];
for (int i = 0; i < n; i++)
for (int j = (int) (sum / 2); j > 0; j--)
if (j >= nums[i])
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
for (int i = 1; i < sum / 2 + 1; i++)
max = max > dp[i] ? max : dp[i];
System.out.println(Math.abs((sum - max) - max));
}
}

0
0 收藏

0 评论
0 收藏
0