第20章 动态规划入门
2020-04-03 本文已影响0人
得力小泡泡
1、蒜头君爬楼梯（一）
算法分析
image.png
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010,mod = 100007;
static int[] f = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
f[0] = 1;
f[1] = 1;
for(int i = 2;i <= 1000;i ++)
f[i] = (f[i - 1] + f[i - 2]) % mod;
System.out.println(f[n]);
}
}
2、蒜头君爬楼梯（二）
算法分析
image.png
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010,mod = 100007;
static int[] f = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
f[0] = 1;
for(int i = 1;i <= 1000;i ++)
{
for(int j = i - 1;j >= 0;j -= 2)
{
f[i] = (f[i] + f[j]) % mod;
}
}
System.out.println(f[n]);
}
}
3、弹簧板（加强版）
算法1
k点能到达i点，则i点向k点连一条有向边
image.png
时间复杂度
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 100100;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0;
static int[] f = new int[N];
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Arrays.fill(h, -1);
for(int i = 1;i <= n;i ++)
{
int x = scan.nextInt();
add(i + x,i);
}
int res = 0;
for(int i = 1;i <= n;i ++)
{
f[i] = 1;
for(int k = h[i];k != -1;k = ne[k])
{
int j = e[k];
f[i] = Math.max(f[i], f[j] + 1);
}
res = Math.max(res, f[i]);
}
System.out.println(idx);
System.out.println(res);
}
}
算法2
和算法1有些区别，若k点能到达i点，则用i的状态去更新k，f[k] = f[i] + 1
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 100100;
static int[] f = new int[N];
static int[] a = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
int res = 0;
for(int i = n;i >= 1;i -- )
{
f[i] = f[i + a[i]] + 1;
res = Math.max(res, f[i]);
}
System.out.println(res);
}
}
4、蒜头君的新游戏
算法分析
image.png
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 35;
static int[][] f = new int[N][N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
f[0][1] = 1;
for(int i = 1;i <= m;i ++)
{
for(int j = 1;j <= n;j ++)
{
int left = j - 1 == 0 ? n : j - 1;
int right = j + 1 == n + 1 ? 1 : j + 1;
f[i][j] = f[i - 1][left] + f[i - 1][right];
}
}
System.out.println(f[m][1]);
}
}
5、逃生
算法分析
此题和摘花生题目类似，不过细节特别多，为了让代码方便，把g[][]数组设为开始的备份数组，从(x1,y1)分别走到左上角，右上角，左下角，右下角，算出生命值最大的值
当前位置由其他位置进行状态转移共3种情况
- 1、
i == x1，只有一个方向转移 - 2、
j == y1，只有一个方向转移 - 3、
i != x1 && j != y1，从两个方向选一个转移
注意：
1、若f[i][j] >= c，需要赋值为c
2、若f[i][j] <= 0，需要赋值为负无穷，当最后的终点小于 -INF / 2表示该人已经死亡，终点位置的值赋值为-1
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010,INF = 0x3f3f3f3f;
static int n,m,x1,y1,v,c;
static int[][] f = new int[N][N];
static int[][] g = new int[N][N];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
x1 = Integer.parseInt(s1[2]);
y1 = Integer.parseInt(s1[3]);
v = Integer.parseInt(s1[4]);
c = Integer.parseInt(s1[5]);
for(int i = 1;i <= n;i ++)
{
String[] s2 = br.readLine().split(" ");
for(int j = 1;j <= m;j ++)
{
f[i][j] = Integer.parseInt(s2[j - 1]);
g[i][j] = Integer.parseInt(s2[j - 1]);
}
}
f[x1][y1] = v;//初始值
g[x1][y1] = v;//初始值
//左上角
for(int i = x1;i >= 1;i --)
{
for(int j = y1;j >= 1;j --)
{
if(i == x1 && j == y1) continue;
if(j == y1) f[i][j] += f[i + 1][j];
else if(i == x1) f[i][j] += f[i][j + 1];
else f[i][j] += Math.max(f[i + 1][j], f[i][j + 1]);
if(f[i][j] >= c) f[i][j] = c;
if(f[i][j] <= 0) f[i][j] = -INF;
}
}
if(f[1][1] < -INF / 2) f[1][1] = -1;
int a1 = f[1][1];
f = g.clone();
//右上角
for(int i = x1;i >= 1;i --)
{
for(int j = y1;j <= m;j ++)
{
if(i == x1 && j == y1) continue;
if(j == y1) f[i][j] += f[i + 1][j];
else if(i == x1) f[i][j] += f[i][j - 1];
else f[i][j] += Math.max(f[i + 1][j], f[i][j - 1]);
if(f[i][j] >= c) f[i][j] = c;
if(f[i][j] <= 0) f[i][j] = -INF;
}
}
if(f[1][m] < -INF / 2) f[1][m] = -1;
int b1 = f[1][m];
f = g.clone();
//左下角
for(int i = x1;i <= n;i ++)
{
for(int j = y1;j >= 1;j --)
{
if(i == x1 && j == y1) continue;
if(j == y1) f[i][j] += f[i - 1][j];
else if(i == x1) f[i][j] += f[i][j + 1];
else f[i][j] += Math.max(f[i - 1][j], f[i][j + 1]);
if(f[i][j] >= c) f[i][j] = c;
if(f[i][j] <= 0) f[i][j] = -INF;
}
}
if(f[n][1] < -INF / 2) f[n][1] = -1;
int c1 = f[n][1];
f = g.clone();
//右下角
for(int i = x1;i <= n;i ++)
{
for(int j = y1;j <= m;j ++)
{
if(i == x1 && j == y1) continue;
if(j == y1) f[i][j] += f[i - 1][j];
else if(i == x1) f[i][j] += f[i][j - 1];
else f[i][j] += Math.max(f[i - 1][j], f[i][j - 1]);
if(f[i][j] >= c) f[i][j] = c;
if(f[i][j] <= 0) f[i][j] = -INF;
}
}
if(f[n][m] < -INF / 2) f[n][m] = -1;
int d1 = f[n][m];
int res = a1;
if(b1 > res) res = b1;
if(c1 > res) res = c1;
if(d1 > res) res = d1;
System.out.println(res);
}
}
6、一维消消乐
算法分析
image.png
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 10010;
static int n;
static int[] a = new int[N];
static int[][] f = new int[N][2];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
String[] s1 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++)
{
a[i] = Integer.parseInt(s1[i - 1]);
}
f[1][0] = 0;
for(int i = 2;i <= n;i ++)
{
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + a[i - 1] * a[i];
}
System.out.println(Math.max(f[n][0], f[n][1]));
}
}
7、数组分组
算法分析
image.png
时间复杂度
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1010;
static int n;
static int[][] mul = new int[N][N];//前缀积
static int[] f = new int[N];
static int[] a = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
mul[i][i] = a[i];
for(int j = i + 1;j <= n;j ++)
{
mul[i][j] = mul[i][j - 1] * a[j] % 1000;
}
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= i;j ++)
{
f[i] = Math.max(f[i], f[j - 1] + mul[j][i]);
}
}
System.out.println(f[n]);
}
}
8、墙壁涂色
算法分析
排列组合环形涂色问题
image.png
设分为n个扇形时染色方法为an种
（1）当n = 2时，A1、A2有3 * 2种，即a2 = 12，a1 = 3
（2）当分成n个扇形，如图，A1与A2不同色，A2与A3不同色..，A(n - 1)与An不同色，共有3 * 2 ^ (n - 1)种，但由于An与A1相邻，所有需要排除An与A1同色的情况，An与A1同色可以将An和A1合并看出一个扇形，与前n - 1个扇形加在一起共n - 1个扇形，此时有a(n - 1)中染法，因此递推公式是
a[n] = 3 * 2 ^ (n - 1) - a[n - 1]
时间复杂度
Java 代码
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
static int N = 55;
static int n;
static Map<Integer,Long> map = new HashMap<Integer,Long>();
static long[] a = new long[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
//预处理出2^1,2^2...2^n
long res = 1;
for(int i = 1;i <= 50;i ++)
{
res *= 2;
map.put(i, res);
}
a[1] = 3;
a[2] = 3 * 2;
for(int i = 3;i <= n;i ++)
{
a[i] = 3 * map.get(i - 1) - a[i - 1];
}
System.out.println(a[n]);
}
}
