DP和DFS+DP详解（Java代码）

解法一： 动态规划
子问题
每个位置拿着k个宝物价值都低于g的方法
确定状态
map[i][j] (i,j)处的宝物价值
dp[i][j][sum][gold] (i,j)处拿着sum个宝物价值都低于gold 的方法数
则结果就是dp[n][m][k][12] 即出口处拿着k个宝物价值都低于12（价值0~12）的方法数
边界状态
在入口处，只有sum=1且gold>入口处宝物价值，或者sum=0，即入口可取时和不取两种情况下，有一可行方法：dp[i][j][sum][gold]=1，其余都为0
因为首行首列也由继承而来，所以(i= =0||j= =0)的时候dp[i][j][sum][gold]=0，计数从1开始
状态转移
拿当前位置的宝物：(gold>map[i][j]&&sum>0)
YES= dp[i-1][j][k-1][sum-1][map[i][j]] (从上边继承)+dp[i][j-1][k-1][map[i][j]] (从左边继承)
不拿当前位置的宝物：
NO= dp[i-1][j][k][c] (从上边继承)+dp[i][j-1][k][c] (从左边继承)
则dp[i][j][k][c]= (YES+NO)

package 蓝桥;
import java.util.Scanner;
public class Main {
    static int n;//行
    static int m;//列
    static int k;//需取数
    static int mod = 1000000007;//取余值
    static int dp[][][][] = new int[51][51][13][13];//x,y,已取数,最大价值
    static int map[][] = new int[51][51];//价值
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <m; j++) {
                map[i+1][j+1] = sc.nextInt();
            }
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                for(int s=0;s<=k;s++) {
                    for(int g=0;g<13;g++) {
                        int YES=0;
                        int NO=0;
                        if(i==1&&j==1){
                            if((s==0||(s==1&&g>map[i][j]))){
                                dp[i][j][s][g]=1;
                            }
                            continue;
                        }
                        if(s>0&&g>map[i][j]) {
                            YES=dp[i-1][j][s-1][map[i][j]]+dp[i][j-1][s-1][map[i][j]];
                            YES%=mod;
                        }
                        NO=dp[i-1][j][s][g]+dp[i][j-1][s][g];
                        NO%=mod;
                        dp[i][j][s][g]=YES+NO;
                        dp[i][j][s][g]%=mod;
                    }
                    }
                }
            }
        System.out.println(dp[n][m][k][12]);
        }
    }

解法二： 深度搜索+记忆化+动态规划
通过DFS从入口开始遍历所有的点，用动态规划计算该点可行方法数并记忆

package 蓝桥;
import java.util.Scanner;
public class Main {
    static int n;//行
    static int m;//列
    static int k;//需取数
    static int mod = 1000000007;//取余值
    static int dp[][][][] = new int[50][50][15][15];//x,y,已取数,最大价值
    static int map[][] = new int[50][50];//价值
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        fill(dp，-1);//因为有的格子不能走，即方法数为0，避免重复搜索，全部置为-1
        System.out.println(dfs(0, 0, 0, -1));//最低价值为0，入口处可取可不取，因此初始最高价值置为-1
    }
    static int dfs(int x, int y, int sum, int max) {
        //越界，比如一直向下一直向右，不可行
        if(x>=n||y>=m||sum>k) {
            return 0;
        }
        //入口的方法数已更新，即已经搜索完毕
        if(dp[x][y][sum][max+1]!=-1) {//因为max初值设为-1，不+1会下越界
            return dp[x][y][sum][max+1];
        }
        int count=0;//方法数
        int gold=map[x][y];//当前位置的价值
        if(x==n-1&&y==m-1) {//到达出口
            //如果已经有K个或者有k-1个且出口处的价值大于手中价值（即可以拿），即为一种可行方法
            if(sum==k||(sum==k-1&&gold>max)) {
                return 1;
            }
            //到达出口但是宝物不够，不可行
            return 0;
        }
        if(gold>max) {//此处可取，取之，每次相加时取余
            count+=dfs(x+1,y,sum+1,gold);
            count%=mod;
            count+=dfs(x,y+1,sum+1,gold);
            count%=mod;
        }
        //不取（不能取和可取但是没有取两种情况）
        count+=dfs(x+1,y,sum,max);
        count%=mod;
        count+=dfs(x,y+1,sum,max);
        count%=mod;
        //记忆
        dp[x][y][sum][max+1]=count;
        return count;
    }
    static void fill(int[][][][] dp2) {
        for (int i = 0; i < 50; i++) {
            for (int j = 0; j < 50; j++) {
                for (int k = 0; k < 15; k++) {
                    for (int l = 0; l < 15; l++) {
                        dp[i][j][k][l] = -1;
                    }
                }
            }
        }
    }
}