# 经典算法之动态规划

### 动态规划的解题核心

#### 题目：求一个数列中最大连续子序列的和。

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

### 动态规划的应用场景

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

```import java.util.Scanner;

/**
* Created by huststl on 2018/3/28 14:24
* 动态规划题01
*
*/
public class Dp01 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);

int n = scan.nextInt();
long max = 0;
int[][] dp = new int[n][n];
dp[0][0] = scan.nextInt();

for(int i=1;i<n;i++){
for(int j=0;j<=i;j++){
int num = scan.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);
}
}```

#### 例题2:编辑距离

```import java.util.Scanner;

/**
* Created by huststl on 2018/3/28 14:44
* 动态规划02
*/
public class dp02 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String aStr = scan.nextLine();
String bStr = scan.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]);
}
}```

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

1 3 3 2 1 3 2 2 1

```import java.util.Scanner;

/**
* Created by huststl on 2018/3/28 14:55
* 矩阵取数问题
*/
public class Dp03 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] dp = 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++){
}
}
System.out.println(dp[n]);
}
}```

#### 例题4:背包问题

```import java.util.Scanner;

/**
* Created by huststl on 2018/3/28 15:06
* 背包问题
*/
public class Dp04 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int v = scan.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] = scan.nextInt();
price[i] = scan.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[i];
}
}

}
for(int i=0;i<v+1;i++){
max = max > dp[i]?max:dp[i];
}
System.out.println(max);
}
}```

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

```import java.util.Scanner;

/**
* Created by huststl on 2018/3/28 15:18
* 最长递增子序列
*/
public class Dp05 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] num = new int[n];
for(int i=0;i<n;i++){
num[i] = scan.nextInt();
}
double[] dou = new double[n+1];
dou[0] = Integer.MIN_VALUE;
dou[1] = num[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(dou[m] < num[i]){
p = m+1;
}else {
r = m-1;
}
}
dou[p] = num[i];
if(p>Len){
Len++;
}
}
System.out.println(Len);
}
}```

https://www.cnblogs.com/xiaoshen666/p/11014954.html

https://www.cnblogs.com/libra-yong/p/6296356.html

0 条评论

• ### 【Netty】ByteBuf （一）

所有的网路通信都涉及字节序列的移动，所以高效易用的数据结构明显是必不可少的。Netty的ByteBuf实现满足并超越了这些需求。

• ### Spring bean的生命周期

Spring中Bean的管理是其最基本的功能，根据下面的图来了解Spring中Bean的生命周期：

• ### 经典算法之bitmap算法

本文将讲述Bit-Map算法的相关原理,Bit-Map算法的一些利用场景，例如BitMap解决海量数据寻找重复、判断个别元素是否在海量数据当中等问题.最后说说B...

• ### Hiho Coder 1038 01背包(模板)

01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi，求将哪些物品装入背包可使获得的价值总和最大。而...

• ### Golang Leetcode 956. Tallest Billboard.go

dp思路 dp方程的键为两个柱子之间的高度差，值为当前高度差情况下，两个柱子的最小高度 状态转移的时候有三种情况，其中后两种可以合并 最后dp[0]保存的...

• ### 利用动态规划求解旅行商问题时空复杂度分析以及相关实验验证

利用动态规划求解旅行商问题（Travelling Salesman Problem，简称TSP）在之前的推文中已经有了详细的介绍，今天我们要对这个问...

• ### 转载 | 利用动态规划求解旅行商问题(Travelling Salesman Problem)时空复杂度分析以及相关实验验证

利用动态规划求解旅行商问题（Travelling Salesman Problem，简称TSP）在之前的推文中已经有了详细的介绍，今天我们要对这个问题进行更深一...

• ### dp考试

a 【问题描述】 ?个物品 ，每个物品都有恰好两。第 ?种物品的体积和价值分别是 ??和??。 背包的体积为 ?，问在不超过背包体积的情况下最多能放进少价值物品...

• ### NYOJ 860 又见01背包(思维)

刚一看这道题以为是01背包的裸题，TLE了一次后发现这是一道拐了个弯的裸题，题中给的物品重量范围太大了，所以我们可以换种思路，把最大价值求出来，然...

• ### 51Nod-1833-环

ACM模版 描述 ? 题解 图论的问题我没有怎么深入学习，多数都是交给了队友去搞，所以看到这个题时，只知道是图上状压 DPDP，却不知道具体从何入手。 看了题解...