第29章 特殊形式的动态规划

1、机器人走方格

算法分析

记忆化搜索

可以知道棋盘中的每个位置走到终点的方案数是固定的，因此搜索过的位置需要进行记录，以免重复搜索，又由于后面的位置的点的结果才能影响到前面的位置的点，因此需要从(0,0)开始进行搜索，往能到达的点进行深度优先搜索

image.png

时间复杂度

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int[][] f = new int[N][N];
    static int[][] a = new int[N][N];
    static int n,m;
    static int mod = 10000;
    static int dfs(int x,int y)
    {
        if(f[x][y] != -1) return f[x][y];
        if(x == n && y == m) return f[x][y] = 1;
        int w = a[x][y];
        long cnt = 0;
        for(int i = x;i <= Math.min(x + w,n);i ++)
            for(int j = y;j <= Math.min(y + w, m);j ++)
            {
                if(i == x && j == y) continue;
                if(i - x + j - y > w) continue;
                cnt = (cnt + dfs(i,j)) % mod; 
            }
        return f[x][y] = (int)cnt;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                a[i][j] = scan.nextInt();
        for(int i = 1;i <= n;i ++)
            Arrays.fill(f[i], -1);
        System.out.println(dfs(1,1));
    }
}

2、肥肥鼠吃奶酪

算法分析

记忆化搜索

题目分析：站在某个位置，能竖直或者水平移动最多m个格子，且移动的格子的能量一定大于当前格子，因此类似滑雪那题

在每个格子中，从这个格子开始dfs找，找到的能量的最大值是固定的，因此可以用记忆化搜索把当前格子的最大能量记录下来，从(1,1)开始，往可以到达的点继续深度优先搜索

时间复杂度

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 110;
    static int[][] f = new int[N][N];
    static int[][] a = new int[N][N];
    static int n,m;
    static int dfs(int x,int y)
    {
        if(f[x][y] != -1) return f[x][y];
        f[x][y] = a[x][y];
        int val = f[x][y];
        for(int i = 1;i <= m;i ++)
        {
            
            if(y - i >= 0 && a[x][y - i] > a[x][y]) val = Math.max(val, dfs(x,y - i) + a[x][y]);
            if(y + i < n && a[x][y + i] > a[x][y]) val = Math.max(val, dfs(x,y + i) + a[x][y]);
            if(x - i >= 0 && a[x - i][y] > a[x][y]) val = Math.max(val, dfs(x - i,y) + a[x][y]);
            if(x + i < n && a[x + i][y] > a[x][y]) val = Math.max(val, dfs(x + i,y) + a[x][y]);
        }
        return f[x][y] = val;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < n;j ++)
                a[i][j] = scan.nextInt();
        for(int i = 0;i < n;i ++)
            Arrays.fill(f[i], -1);
        System.out.println(dfs(0,0));
    }
}