第20章 动态规划入门

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]);
    }
}