参考各位大佬的代码

递归(超时)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    private static final int mod = 1000000007;
    private static int n, m, k;
    private static int[][] w;
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static PrintWriter writer = new PrintWriter(System.out);
    private static int dfs(int r, int c, int num, int max) {
        // 判断越界
        if (r > n || c > m || num > k) return 0;
        // 走到终点
        if (r == n && c == m) 
            return (num == k || (w[r][c] > max && num + 1 == k)) ? 1 : 0;
        if (w[r][c] > max)
            return dfs(r, c + 1, num + 1, w[r][c]) + dfs(r, c + 1, num, max) +
                    dfs(r + 1, c, num + 1, w[r][c]) + dfs(r + 1, c, num, max);
        else return dfs(r, c + 1, num, max) + dfs(r + 1, c, num, max);
    }
    public static void main(String[] args) throws IOException{
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        w = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i ++) {
            s = reader.readLine().split(" ");
            for (int j = 1; j <= m; j ++) {
                w[i][j] = Integer.parseInt(s[j - 1]);
            }
        }

        reader.close();
        writer.print(dfs(1, 1, 0, -1) % mod);
        writer.flush();
        writer.close();

    }
}

递归变换动态规划

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    private static final int mod = 1000000007;
    private static int n, m, k;
    private static int[][] w;
    private static int[][][][] f;
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static PrintWriter writer = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException{
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        w = new int[n + 1][m + 1];
        f = new int[n + 2][m + 2][k + 2][14];
        for (int i = 1; i <= n; i ++) {
            s = reader.readLine().split(" ");
            for (int j = 1; j <= m; j ++) {
                w[i][j] = Integer.parseInt(s[j - 1]);
                w[i][j] ++;
            }
        }

        for (int v = 1; v <= 13; v ++) {
            f[n][m][k][v] = 1;
            if (w[n][m] > v) f[n][m][k - 1][v] = 1;
        }

        for (int i = n; i >= 1; i --)
            for (int j = m; j >= 1; j --)
                for (int u = k; u >= 0; u --)
                    for (int v = 13; v >= 0; v --) {
                        // 状态在上面已经初始过需要跳过边界
                        if (i == n && j == m && (u == k || u == k - 1)) continue;
                        if (w[i][j] > v) // 因为可选可不选所以方案数等于不选+选的
                            f[i][j][u][v] = ((f[i + 1][j][u][v] + f[i][j + 1][u][v]) % mod + 
                                    (f[i + 1][j][u + 1][w[i][j]] + f[i][j + 1][u + 1][w[i][j]]) % mod) % mod;
                        else // 因为不可选可不选所以方案数等于不选的
                            f[i][j][u][v] = (f[i + 1][j][u][v] + f[i][j + 1][u][v]) % mod;
                    }

        writer.print(f[1][1][0][0]);

        reader.close();
        writer.flush();
        writer.close();

    }
}

y总动态规划

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    private static final int mod = 1000000007;
    private static int n, m, k;
    private static int[][] w;
    private static int[][][][] f;
    /*
     * f[i][j][k][c]:所有从起点走到(i,j)，且已经取得了k件物品，且最后一件物品是c的合法方案的集合
     * */
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static PrintWriter writer = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException{
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        w = new int[n + 1][m + 1];
        f = new int[n + 1][m + 1][k + 1][14];
        for (int i = 1; i <= n; i ++) {
            s = reader.readLine().split(" ");
            for (int j = 1; j <= m; j ++) {
                w[i][j] = Integer.parseInt(s[j - 1]);
                w[i][j] ++;
            }
        }
        //两个边界初始化
        //在起点(1, 1)处
        //如果拿也只能拿w[i][j]这个物品，只有一种方案
        //如果不拿，那就是0个物品，也是一个方案数
        //由于物品价值已经增加了一个偏移量，现在价值的范围是[1, 13]
        //所以价值为0并不代表物品的价值，而是一个边界点
        f[1][1][0][0] = 1;  // 不拿第一个
        f[1][1][1][w[1][1]] = 1;    // 拿第一个

        /* 枚举可能转移到当前状态的状态 */
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                for (int u = 0; u <= k; u ++)
                    for (int v = 0; v <= 13; v ++) {
                        // 不拿物品
                        f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u][v]) % mod;
                        f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u][v]) % mod;
                        // 可以拿物品
                        if (u > 0 && v == w[i][j]) {
                            // 最终的选择到了最大的价值宝物（因为题目递增），且有选择次数，则累加不同价值的子集
                            // 当前的方案数量=上一步的所有价值的方案数量之和 最长递增子序列
                            for (int c = 0; c < v; c ++) {
                                f[i][j][u][v] = (f[i][j][u][v] + f[i - 1][j][u - 1][c]) % mod;
                                f[i][j][u][v] = (f[i][j][u][v] + f[i][j - 1][u - 1][c]) % mod;
                            }
                        }
                    }

        int res = 0;
        // 总方案数量等于当前数量下所有价值的数量总和
        for (int i = 1; i <= 13; i ++) res = (res + f[n][m][k][i]) % mod;
        writer.print(res);

        reader.close();
        writer.flush();
        writer.close();

    }
}

另一种思路的动态规划

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class AcWing1212地宫取宝3 {
    private static final int mod = 1000000007;
    private static int n, m, k;
    private static int[][] w;
    private static int[][][][] f;
    /*
     * f[i][j][k][c]:所有从起点走到(i,j)，且已经取得了k件物品，且最后一件物品是c的合法方案的集合
     * */
    private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static PrintWriter writer = new PrintWriter(System.out);
    public static void main(String[] args) throws IOException{
        String[] s = reader.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        w = new int[n + 2][m + 2];
        f = new int[n + 2][m + 2][13][14];
        for (int i = 1; i <= n; i ++) {
            s = reader.readLine().split(" ");
            for (int j = 1; j <= m; j ++) {
                w[i][j] = Integer.parseInt(s[j - 1]);
                w[i][j] ++;
            }
        }
        //两个边界初始化
        //在起点(1, 1)处
        //如果拿也只能拿w[i][j]这个物品，只有一种方案
        //如果不拿，那就是0个物品，也是一个方案数
        //由于物品价值已经增加了一个偏移量，现在价值的范围是[1, 13]
        //所以价值为0并不代表物品的价值，而是一个边界点
        f[1][1][0][0] = f[1][1][1][w[1][1]] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                for (int u = 0; u <= k; u ++ )
                    for (int v = 0; v < 14; v ++ )
                        if (f[i][j][u][v] > 0)
                        {
                            // 不取(i+1,j)的物品，可以直接从(i,j)转移到(i+1,j)
                            f[i + 1][j][u][v] = (f[i + 1][j][u][v] + f[i][j][u][v]) % mod;
                            // 不取(i,j+1)的物品，可以直接从(i,j)转移到(i,j+1)
                            f[i][j + 1][u][v] = (f[i][j + 1][u][v] + f[i][j][u][v]) % mod;

                            // 还可以取物品
                            if (u + 1 <= k)
                            {
                                // 取(i+1,j)的物品，从(i,j)转移到(i+1,j)
                                if (w[i + 1][j] > v) f[i + 1][j][u + 1][w[i + 1][j]] = (f[i + 1][j][u + 1][w[i + 1][j]] + f[i][j][u][v]) % mod;
                                // 取(i,j+1)的物品，从(i,j)转移到(i,j+1)
                                if (w[i][j + 1] > v) f[i][j + 1][u + 1][w[i][j + 1]] = (f[i][j + 1][u + 1][w[i][j + 1]] + f[i][j][u][v]) % mod;
                            }
                        }


        int res = 0;
        // 总方案数量等于当前数量下所有价值的数量总和
        for (int i = 1; i <= 13; i ++) res = (res + f[n][m][k][i]) % mod;
        writer.print(res);

        reader.close();
        writer.flush();
        writer.close();

    }
}