动态规划之数组压缩空间、星号技巧【3】

亦凉 2024-04-05 05:47 88阅读 0赞

## 动态规划之数组压缩空间、星号技巧【3】 ##

### 1 最小距离累加和 ###

![在这里插入图片描述][2b5b119aa0c04ba4a0a115d32fb1d7fc.png]

#### 1.1 正常动规 ####

//正常动态规划
    public static int minPathSum1(int[][] m){
        
        //边界
        if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
        
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        //初始位置[0, 0] 不依赖于任何位置,只看自己的值
        dp[0][0] = m[0][0];
        //第一行
        for(int i = 1; i < col; i++){
        
            //对于每一列来说
            dp[0][i] = dp[0][i-1] + m[0][i];
        }
        //第一列
        for(int j = 1; j < row; j++){
        
            //对于每一行来说
            dp[j][0] = dp[j-1][0] + m[j][0];
        }
        //普遍范围
        for(int i = 1; i < row; i++){
        
            for(int j = 1; j < col; j++){
        
                //每一个位置都依赖于它的上左
                //可以选择左边也可以选择上边
                //选择最小的那个
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + m[i][j];
            }
        }
        return dp[row-1][col-1];
    }

`思考：如果题目所给的数组，有太多行怎么办呢？`

> 可以将动态规划表，改为一维数组，如果行太多，则改成一行N列的一维数组

//压缩空间【时间复杂度不变】
    public static int minPathSum2(int[][] m){
        
        if(m == null || m.length == 0 || m[0].length == 0 || m[0] == null){
        
            return 0;
        } 
        int row = m.length;
        int col = m[0].length;
        //假设行太多
        int[] dp = new int[col];
        dp[0] = m[0][0];
        //初始化数组[填充之前的第一行]
        for(int j = 1; j < col; j++){
        
            dp[j] = dp[j-1] + m[0][j];
        }
        //压缩空间
        for(int i = 1; i < row; i++){
        
            //记住最左边位置【之前的第一列】
            dp[0] += m[i][0];
            for(int j = 1; j < col; j++){
        
                //dp[j]：相当于之前的上方
                //dp[j-1]:相当于之前左方
                dp[j] = Math.min(dp[j-1], dp[j]) + m[i][j];
            }
        }
        return dp[col-1];
    }

### 2 货币问题1【面值相同为两张、张数无限】 ###

![在这里插入图片描述][3472f0b2f97247e2b66760c62eada7ae.png]

#### 2.1 递归尝试 ####

//arr:钱币数组
    //aim:目标值
    public static int coinWays(int[] arr, int aim) {
        
        return process(arr, 0, aim);
    }
    
    //arr:钱币数组
    //index:当前所在位置
    //rest:剩余的目标钱数
    public static int process(int[] arr, int index, int rest) {
        
        if (rest < 0) {
        
            //剩余钱数小于零
            return 0;
        }
        if (index == arr.length) {
        
            return rest == 0 ? 1 : 0;
        } else {
        
            //选当前硬币与不选当前硬币【方法数和】
            return process(arr, index + 1, rest) + process(arr, index + 1, rest - arr[index]);
        }
    }

#### 2.2 动态规划 ####

//动态规划
    public static int dp(int[] arr, int aim){
        
        int N = arr.length;
        //0-aim 共有aim+1个数
        //arr.length同理【会取到结尾就+1】
        int[][] dp = new int[N+1][aim+1];
        //base case【index为数组末尾， rest为0时候】
        dp[N][0] = 1;
        for(int index = N - 1; index >= 0; index--){
        
            for(int rest = aim; rest >= 0; rest--){
        
                dp[index][rest] = dp[index+1][rest] + (rest - arr[index] >= 0 ? dp[index+1][rest - arr[index]] : 0);
            }
        }
        return dp[0][aim];
    }

### 3 货币问题2【面值相同为一张、张数无限】 ###

![在这里插入图片描述][bf61f19fa14c4f0eb1c145ef6d03c252.png]

#### 3.1 尝试（zhang） ####

public static int coinsWay(int[] arr, int aim){
        
        if(arr == null || arr.length == 0 || aim < 0){
        
            return 0;
        }
        return process(arr, 0, aim);
    }
    
    //大体思路和货币问题1一样【只不过多了一层for循环，需要做暴力尝试】
    public static int process(int[] arr, int index, int rest){
        
        if(index == arr.length){
        
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        //张数可以能为0，可能不为0【包含了选该货币和不选该货币的情况】
        for(int zhang = 0; zhang * arr[index] <= rest; zhang++){
        
            ways += process(arr, index+1, rest - zhang * arr[index]);
        }
        return ways;
    }

#### 3.2 动态规划1（三层for） ####

//动态规划1：三层for循环
    public static int dp1(int[] arr, int aim) {
        
        if (arr == null || arr.length == 0) {
        
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        //index+1 -> 上面的依赖下面的
        for (int index = N - 1; index >= 0; index--) {
        
            for (int rest = aim; rest >= 0; rest--) {
        
                //穷举：张数
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
        
                    ways += dp[index + 1][rest - zhang * arr[index]];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

#### 3.2 动态规划2 ####

//建立空间感：优化【√ = ※ + a】
    //  ※   √
    //      a
    public static int dp2(int[] arr, int aim) {
        
        if (arr == null || arr.length == 0 || aim < 0) {
        
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
        
            for (int rest = aim; rest >= 0; rest--) {
        
                //画格子：找规律    8      11      14  (建立空间感)
                //           3张3元    2张3元    1张3元
                //  ※   √
                //①获得我下面格子的值a
                dp[index][rest] = dp[index + 1][rest];
                //②如果没有越界，我直接获得我※号的位置
                if (rest - arr[index] >= 0) {
        
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

### 4 货币问题3【每个值都是一张货币，张数有限】 ###

![在这里插入图片描述][ab105060333a43b2aa7e7f40de74381f.png]

#### >>前置类及方法 ####

//收集纸币信息
    public static class Info {
        
        //有哪些纸币
        public int[] coins;
        //每种纸币对应的张数
        public int[] zhangs;
    
        public Info(int[] coins, int[] zhangs) {
        
            this.coins = coins;
            this.zhangs = zhangs;
        }
    }
    
    //收集纸币信息[不同纸币对应数量]
    public static Info getInfo(int[] arr) {
        
        Map<Integer, Integer> map = new Hashtable<>();
        for (int i = 0; i < arr.length; i++) {
        
            if (map.containsKey(arr[i])) {
        
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
        
                map.put(arr[i], 1);
            }
        }
        int N = map.size();
        int[] coins = new int[N];
        int[] zhangs = new int[N];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }

#### 4.1 尝试（收集纸币信息） ####

//方法入口
    public static int coinsWay(int[] arr, int aim) {
        
        if (arr == null || arr.length == 0 || aim < 0) {
        
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        return process(coins, zhangs, 0, aim);
    }
    
    //递归调用方法
    public static int process(int[] coins, int[] zhangs, int index, int rest) {
        
        int N = coins.length;
        if (index == N) {
        
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for(int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++){
        
            ways += process(coins, zhangs, index+1, rest - zhang*coins[index]);
        }
        return ways;
    }

#### 4.2 动态规划第一个版本（三个for） ####

//动态规划：第一个版本
    public static int dp1(int[] arr, int aim){
        
        if(arr == null || arr.length == 0 || aim < 0){
        
            return 0;
        }
        Info info = getInfo(arr);
        //纸币数组
        int[] coins = info.coins;
        //每种纸币对应的张数
        int[] zhangs = info.zhangs;
        int N = coins.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for(int i = N - 1; i >= 0; i--){
        
            for(int rest = aim; rest >= 0; rest--){
        
                int ways = 0;
                for(int zhang = 0; zhang * coins[i] <= rest && zhang <= zhangs[i]; zhang++){
        
                    ways += dp[i+1][rest - zhang*coins[i]];
                }
                dp[i][rest] = ways;
            }
        }
        return dp[0][aim];
    }

#### 4.3 动态规划第二个版本（√、※） ####

//动态规划2：画表格，建立空间感，找规律
    public static int dp2(int[] arr, int aim) {
        
        if (arr == null || arr.length == 0 || aim < 0) {
        
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        //纸币的种类
        int N = coins.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
        
            //一行中的元素之间如果没有依赖，所以无论从左往右还是从右往左都可以【此处只能从左往右：因为我们在技巧上要依赖它的左边※】
            for (int rest = 0; rest <= aim; rest++) {
        
                //画表格，建立空间感，找规律
                //      ※    √
                // x          a(多算了一个x)
                dp[index][rest] = dp[index + 1][rest];
                if (rest - coins[index] >= 0) {
        
                    dp[index][rest] += dp[index][rest - coins[index]];
                }
                //判断是否多算
                if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
        
                    dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)];
                }
            }
        }
        return dp[0][aim];
    }

### 5 圈问题【Bob Die】 ###

![在这里插入图片描述][0d0c2359ba9f424b8a42ee2c37c55d54.png]

#### 5.1 递归尝试 ####

//row * col 范围
    //N * M 存活区域，超过该区域，bob掉沟里，死亡
    //k bob一共走k步
    public static double livePossibility1(int row, int col, int k, int N, int M) {
        
        return (double) process(row, col, k, N, M) / Math.pow(4, k);
    }
    
    //目前在row、col位置，还有rest步要走，走完了如果还在范围内，就获得一个生存点，返回总的生存点数
    public static long process(int row, int col, int rest, int N, int M) {
        
        if (row < 0 || row == N || col < 0 || col == M) {
        
            return 0;
        }
        //还在棋盘中
        if (rest == 0) {
        
            return 1;
        }
        //还在棋盘中，且还有步数要走
        long up = process(row - 1, col, rest - 1, N, M);
        long down = process(row + 1, col, rest - 1, N, M);
        long left = process(row, col - 1, rest - 1, N, M);
        long right = process(row, col + 1, rest - 1, N, M);
        return up + down + left + right;
    }

#### 5.2 动态规划（三维） ####

//三维动态规划【三个变量】
    public static double livePossibility2(int row, int col, int k, int N, int M){
        
    	//根据N * M范围建立矩阵即可【取不到N、M】
        long[][][] dp = new long[N][M][k+1];
        // 根据尝试：rest == 0 -> 返回1
        for(int i = 0; i < N; i++){
        
            for(int j = 0; j < M; j++){
        
                dp[i][j][0] = 1;
            }
        }
        for(int rest = 1; rest <= k; rest++){
        
            for(int r = 0; r < N; r++){
        
                for(int c = 0; c < M; c++){
        
                    dp[r][c][rest] = pick(dp, N, M, r-1, c, rest-1);
                    dp[r][c][rest] += pick(dp, N, M, r+1, c, rest-1);
                    dp[r][c][rest] += pick(dp, N, M, r, c-1, rest-1);
                    dp[r][c][rest] += pick(dp, N, M, r, c+1, rest-1);
                }
            }
        }
        return (double) dp[row][col][k] / Math.pow(4, k);
    }
    
    //控制范围【防止越界还计算】
    public static long pick(long[][][] dp, int N, int M, int r, int c, int rest){
        
        if(r < 0 || r == N || c < 0 || c == M){
        
            return 0;
        }
        return dp[r][c][rest];
    }

[2b5b119aa0c04ba4a0a115d32fb1d7fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/81618fd17ced415bab784daabd335655.png
[3472f0b2f97247e2b66760c62eada7ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/6128b28dfa584f5a90a792f50c66a19e.png
[bf61f19fa14c4f0eb1c145ef6d03c252.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/9b8c76635d69458b8a9f5cbeb80ada16.png
[ab105060333a43b2aa7e7f40de74381f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/87aacc1d0ce748e09e6f589a636085d0.png
[0d0c2359ba9f424b8a42ee2c37c55d54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/04/e9411b5285494933827a6d99d59a23e9.png