【算法&数据结构体系篇class21】：暴力递归到动态规划

港控/mmm° 2024-03-24 08:28 19阅读 0赞

### 一、矩阵走路 ###

> 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角  
> 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和  
> 返回最小距离累加和

package class21;
    
    /**
     * 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
     * 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
     * 返回最小距离累加和
     */
    public class MinPathSum {
        //方法一 动态规划 二维数组
        public static int minPathSum1(int[][] m){
            //边界的判断 注意每行 以及行中 是否为空 长度0
            if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
                return 0;
            }
            int row = m.length;     //行
            int col = m[0].length;  //列
    
            //分析题意是一个二维数组，从0,0出发 到row-1,col-1 右下角  对应可定义一个等规模二维数据dp
            int[][] dp = new int[row][col];
            dp[0][0] = m[0][0];          //0，0位置就是对应起始点 等值与m[0][0]，先赋值好
            //分析依赖情况：只可以向下 向右， 那么第一行 是顶行 [0][1]只依赖[0][1]左边的值，没有上边的值了
            //填充第一行
            for(int i = 1; i < col; i++){
                dp[0][i] = dp[0][i-1] + m[0][i];  //第一行 i位置值就是累加i-1的值和当前m[0][i]的值
            }
            //同理分析第一列 只依赖上位置，因为已经是最左侧了 没有左边的值了 只能往下走 依赖上位置
            for(int i = 1; i < row; i++){
                dp[i][0] = dp[i-1][0] + m[i][0];
            }
    
            //此时已经填充完 第一行 第一列 接着就分析填充完剩余位置
            //往下和往右 表示依赖上位置和左位置 ，那么我们就依次从 dp[1][1]这个位置开始 也就是第二行第二列 依次从左往右遍历完第二行
            //接着来到第三行第二列 依次循环到最后行
            for(int i = 1; i < row; i++){
                for(int j = 1; j < col; j++){
                    //来到[i][j]位置 他是从上位置[i-1][j] 或者 左位置[i][j-1]两种可能位置走到的，那么求最小距离和，我们就选两个方向的较小值路径，再加上本身位置的值，那么就得到dp[i][j]最小值
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + m[i][j];
                }
            }
            return dp[row-1][col-1];   //因为我们定义的二维数组 就是从左上角[0][0]开始走到右下角[row-1][col-1]的路径和 那么就是返回最右下角的位置值
        }
    
    
        //方法二 动态规划  空间压缩优化 一维数组
        public static int minPathSum2(int[][] m){
            //边界的判断 注意每行 以及行中 是否为空 长度0
            if(m == null || m.length == 0 || m[0] == null || m[0].length == 0){
                return 0;
            }
    
            //根据题意，我们可得到，其实不需要整个矩阵空间，因为每个位置依赖与当前行左位置和上一行位置，因此我们可压缩到
            //一个数组 长度为列数，依次刷新每一行的值 最后返回arr[col-1]
            int row = m.length;     //行数
            int col = m[0].length;  //列数
    
            int[] dp = new int[col];
            dp[0] = m[0][0];        //初始值 第一个元素值就是矩阵的第一行第一列0,0
            for(int i = 1; i < col;i++){
                dp[i] = dp[i-1] + m[0][i];    //初始值第一行的值。 第一行只依赖左位置，因为没有上位置走下来，已经是顶行 然后再加上当前矩阵对应位置的数值
            }
    
            //开始刷新第二行到最后一行
            for(int i = 1; i < row; i++){
                //需要先刷新第一列的值，就是dp[0],从上一行的值替换下一行的值 。该值只依赖上位置 因为没有左位置了所以不依赖左位置 再加上当前矩阵对应位置的值
                dp[0] +=  m[i][0];    //累加下一行第一列的值m[i][0]
                for(int j = 1; j < col; j++){
                    //接着刷新dp[1....] 刷新当前行的 第二列往最后一列的值 取dp[j-1] 左位置 和 dp[j]上位置的较小值,此时没刷新时dp[j] 就是上位置值 ； 再加上 m[i][j]当前位置的值
                    dp[j] = Math.min(dp[j-1],dp[j]) + m[i][j];
                }
            }
            return dp[col-1];  //最后返回 该数组最后一个位置的值 当前已经刷新到最后一行,所以最后一个索引 就是矩阵右下角的位置
        }
    
        // for test
        public static int[][] generateRandomMatrix(int rowSize, int colSize) {
            if (rowSize < 0 || colSize < 0) {
                return null;
            }
            int[][] result = new int[rowSize][colSize];
            for (int i = 0; i != result.length; i++) {
                for (int j = 0; j != result[0].length; j++) {
                    result[i][j] = (int) (Math.random() * 100);
                }
            }
            return result;
        }
    
        // for test
        public static void printMatrix(int[][] matrix) {
            for (int i = 0; i != matrix.length; i++) {
                for (int j = 0; j != matrix[0].length; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            int rowSize = 10;
            int colSize = 10;
            int[][] m = generateRandomMatrix(rowSize, colSize);
            System.out.println(minPathSum1(m));
            System.out.println(minPathSum2(m));
    
        }
    }

### 二、货币问题 （只有一张、每张都不一样） ###

> arr是货币数组，其中的值都是正数。再给定一个正数aim。  
> 每个值都认为是一张货币，  
> 即便是值相同的货币也认为每一张都是不同的，  
> 返回组成aim的方法数  
> 例如：arr = \{1,1,1\}，aim = 2  
> 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2  
> 一共就3种方法，所以返回3

package class21;
    
    /**
     * arr是货币数组，其中的值都是正数。再给定一个正数aim。
     * 每个值都认为是一张货币，
     * 即便是值相同的货币也认为每一张都是不同的，
     * 返回组成aim的方法数
     * 例如：arr = {1,1,1}，aim = 2
     * 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
     * 一共就3种方法，所以返回3
     */
    public class CoinsWayEveryPaperDifferent {
    
        //方法一： 暴力递归
        public static int coinWays(int[] arr, int aim){
            //从左往右类型题  我们定义从arr[0]开始从左往右选择得到aim的方法数
            return process(arr, 0, aim);
        }
    
        //递归函数     货币数组arr 从[index...]区间 选择货币得到 当前aim的方法数返回 当前[0...index-1]已经选择好了
        public static int process(int[] arr, int index, int aim){
            //base case 如果位置来到越界 说明没有货币了 ，那么如果当前aim所剩值为0 说明前面已经凑齐 返回1 否则返回0
            if(index == arr.length){
                return aim == 0 ? 1 : 0;  //凑齐那么就返回1 种方法累加 否则就是当前时0种
            }
    
            //base case 如果目标值aim 减到了负数 那么表示没有凑整，返回0种方法
            if(aim < 0) return 0;
    
            //接着分析情况，当前inex 是否选取， 不选 aim不变 index+1   选 aim就减去当前货币值 index-1
            //结果要返回全部的方法数 那么就是将 选和不选 两种方式都相加返回
            return process(arr, index+1, aim) + process(arr, index + 1, aim - arr[index]);
        }
    
    
        //方法二：动态规划
        public static int dp(int[] arr, int aim){
            //分析递归函数的可变参数 index 货币数组下标 范围0-N， aim 负数-aim 负数坐标无效忽略 0-aim
            int n = arr.length;
            int[][] dp = new int[n+1][aim+1];
            dp[n][0] = 1;          //base case 货币数组索引越界来到n行 对应的目标值为0 也就是第一列 值为1 其他列为0 默认值都是0 不需处理
            //分析递归依赖 index 依赖 index+1 也就是 上行依赖下行 当前我们已经填充好最后一行，那么填充数据就从下往上一行行填充就可完成
            for(int i = n-1 ; i >=0; i--){    //第n 行 货币
                for(int j = 0; j <= aim; j++){  //第n 列 目标值
                    //注意这里 递归中 当前索引选择货币 时 目标值减去索引货币值 这个aim目标递归时会来到负数，要返回0的 属于越界情况，需要判断(j - arr[i]) 目标值-索引货币值后是否小于0了 不小于就说明不越界 可以依赖 越界则返回0
                    dp[i][j] = dp[i+1][j] + ((j - arr[i]) >= 0 ? dp[i+1][j-arr[i]] : 0);
                }
            }
            return dp[0][aim];  //根据递归函数 是传递0索引开始 目标值aim 对应返回dp数组位置值
        }
    
        // 为了测试
        public static int[] randomArray(int maxLen, int maxValue) {
            int N = (int) (Math.random() * maxLen);
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = (int) (Math.random() * maxValue) + 1;
            }
            return arr;
        }
    
        // 为了测试
        public static void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // 为了测试
        public static void main(String[] args) {
            int maxLen = 20;
            int maxValue = 30;
            int testTime = 1000000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr = randomArray(maxLen, maxValue);
                int aim = (int) (Math.random() * maxValue);
                int ans1 = coinWays(arr, aim);
                int ans2 = dp(arr, aim);
                if (ans1 != ans2) {
                    System.out.println("Oops!");
                    printArray(arr);
                    System.out.println(aim);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    }

### 三、货币问题 （无限张、每张都不一样） ###

> arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。  
> 每个值都认为是一种面值，且认为张数是无限的。  
> 返回组成aim的方法数  
> 例如：arr = \{1,2\}，aim = 4  
> 方法如下：1+1+1+1、1+1+2、2+2  
> 一共就3种方法，所以返回3

package class21;
    
    /**
     * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
     * 每个值都认为是一种面值，且认为张数是无限的。
     * 返回组成aim的方法数
     * 例如：arr = {1,2}，aim = 4
     * 方法如下：1+1+1+1、1+1+2、2+2
     * 一共就3种方法，所以返回3
     */
    public class CoinsWayNoLimit {
    
        //方法一： 暴力递归
        public static int coinsWay(int[] arr, int aim) {
            //直接调用暴力递归  从左到右 0位置开始
            return process(arr, 0, aim);
        }
    
        //递归函数， arr[index....]往右选择货币组成 aim目标值的方法数
        public static int process(int[] arr, int index, int aim) {
            //base case 索引来到越界处，如果当前aim剩余0 说明前面的选择是一种方法 返回1  否则就返回0
            if (index == arr.length) {
                return aim == 0 ? 1 : 0;
            }
            //这里不需要再进行 aim<0的一个判断 因为下面的循环中会有控制aim不小于0
    
            //先定义一个方法数 初始化为0
            int ways = 0;
            //分析题意，当前是每张货币是无限张，所以每一个货币 就不是只有 要或者不要的选择了，是可选择0，1，2，3...张货币值，而张数*货币值不能大于目标值
            //也就是 张数遍历条件是 (count * arr[index]) <= aim
            for (int count = 0; (count * arr[index]) <= aim; count++) {
                //方法数累加 0张时，也就是当前index不选 来到下个货币index+1， 目标值- 0张index货币值
                //           1张时， index选择了，来到下个货币index+1, 目标值-1张index货币值...
                ways += process(arr, index + 1, aim - (count * arr[index]));
            }
            return ways;
        }
    
        //方法二：动态规划
        public static int dp1(int[] arr, int aim) {
            //可变参数 index 范围是 0，arr.length  aim目标值 范围是 0，aim
            int n = arr.length;
            int[][] dp = new int[n + 1][aim + 1];
            dp[n][0] = 1;        //base case 索引来到越界处，如果当前aim剩余0 说明前面的选择是一种方法 返回1  否则就返回0  默认数组值就是0 所以无需处理 第N行最后一行处理完成
    
    
            //分析递归依赖， index 依赖 index+1  也就是 上一行依赖下一行 0行依赖1行 因为前面我们把最后一行填充完成了 所以可从下往上取填充 n-1依赖n行
            for (int index = n - 1; index >= 0; index--) {  //每一行  货币值
                for (int rest = 0; rest <= aim; rest++) { //每一列  目标值
                    int ways = 0;     //初始化方法数 0  当前index行 依赖的index+1行的某些列 累计完后 到下个index,这个ways就需要从0开始计算
                    //这里根据递归函数，每个位置并不是常数操作就得到的 而是经过一个循环O(N)得到 说明是依赖了N个值累加而来
                    for (int count = 0; count * arr[index] <= rest; count++) {
                        //方法数累加 0张时，也就是当前index不选 来到下个货币index+1， 目标值- 0张index货币值
                        //           1张时， index选择了，来到下个货币index+1, 目标值-1张index货币值...
                        ways += dp[index + 1][rest - (count * arr[index])];
                    }
                    dp[index][rest] = ways;    //方法数计算完当前位置时 就赋值回去
                }
            }
            return dp[0][aim];  //根据递归的主程序 调用输入是0位置货币 以及aim目标值 带入对应dp数组位置返回
        }
    
    
        //方法三：动态规划  优化时间复杂度 因为dp1方法中，填充每个值，用到了循环，而不是一个常数复杂度的赋值
        public static int dp2(int[] arr, int aim) {
            //可变参数 index 范围是 0，arr.length  aim目标值 范围是 0，aim
            int n = arr.length;
            int[][] dp = new int[n + 1][aim + 1];
            dp[n][0] = 1;        //base case 索引来到越界处，如果当前aim剩余0 说明前面的选择是一种方法 返回1  否则就返回0  默认数组值就是0 所以无需处理 第N行最后一行处理完成
    
    
            //分析递归依赖， index 依赖 index+1  也就是 上一行依赖下一行 0行依赖1行 因为前面我们把最后一行填充完成了 所以可从下往上取填充 n-1依赖n行
            for (int index = n - 1; index >= 0; index--) {  //每一行  货币值
                for (int rest = 0; rest <= aim; rest++) { //每一列  目标值
    
                    //dp1赋值方式中我们假设一个例子 index = 3,rest=13 dp[3][13]  arr[3]=3; 也就是第4行第14列 arr[3]的货币值是3
                    //开始遍历 count =0 张时 ways = dp[4][13-0*3] = dp[4][13]  也就是第5行第14列 依赖下位置
                    //count =1 张时 way += dp[4][13-1*3] = dp[4][10]                第5行第11列 来到下位置的左边算3个位置
                    //count =2 张时 way += dp[4][13-2*3] = dp[4][7]                第5行第8列 来到下位置的左边算6个位置
                    //count =3 张时 way += dp[4][13-3*3] = dp[4][4]                第5行第8列 来到下位置的左边算9个位置
                    //count =4 张时 way += dp[4][13-4*3] = dp[4][1]                第5行第8列 来到下位置的左边算12个位置
                    //count =5 张时 way += dp[4][13-5*3] = dp[4][-2]               这里列数已经越界 所以不会遍历 不依赖
                    //这里可以得到确实依赖了有N个，那么我们就转换成常数个把！
                    //我们看看 index = 3,rest=10 dp[3][10] arr[3]同样也是货币值是3 因为对应index行数一样 行数代表的货币值。 这个位置就在dp[3][13]的左位置算货币值3个位置
                    //那么这个左位置dp[3][12] 怎么依赖，  同理 也是从count =0...一直到count = 3 dp[3][10 - 3*3] = dp[4][1],再往下就越界 并且这四张对应前面从count = 1 张往后的四个货币值
                    //由此规律可转换得到  dp[3][13] = dp[4][13] 下位置 +  dp[3][10] 左位置往arr[3]这个货币值的个数位置
    
                    dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index][rest - arr[index]] : 0);
                }
            }
            return dp[0][aim];    //递归主程序 调用0索引 aim目标值 那么对应就返回dp数组的值
        }
    
    
        // 为了测试
        public static int[] randomArray(int maxLen, int maxValue) {
            int N = (int) (Math.random() * maxLen);
            int[] arr = new int[N];
            boolean[] has = new boolean[maxValue + 1];
            for (int i = 0; i < N; i++) {
                do {
                    arr[i] = (int) (Math.random() * maxValue) + 1;
                } while (has[arr[i]]);
                has[arr[i]] = true;
            }
            return arr;
        }
    
        // 为了测试
        public static void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // 为了测试
        public static void main(String[] args) {
            int maxLen = 10;
            int maxValue = 30;
            int testTime = 1000000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr = randomArray(maxLen, maxValue);
                int aim = (int) (Math.random() * maxValue);
                int ans1 = coinsWay(arr, aim);
                int ans2 = dp1(arr, aim);
                int ans3 = dp2(arr, aim);
                if (ans1 != ans2 || ans1 != ans3) {
                    System.out.println("Oops!");
                    printArray(arr);
                    System.out.println(aim);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println(ans3);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    }

### 四、货币问题 （只有一张、值相同货币是认为是一样的） ###

> arr是货币数组，其中的值都是正数。再给定一个正数aim。  
> 每个值都认为是一张货币，  
> 认为值相同的货币没有任何不同，  
> 返回组成aim的方法数  
> 例如：arr = \{1,2,1,1,2,1,2\}，aim = 4  
> 方法：1+1+1+1、1+1+2、2+2  
> 一共就3种方法，所以返回3

package class21;
    
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * arr是货币数组，其中的值都是正数。再给定一个正数aim。
     * 每个值都认为是一张货币，
     * 认为值相同的货币没有任何不同，
     * 返回组成aim的方法数
     * 例如：arr = {1,2,1,1,2,1,2}，aim = 4
     * 方法：1+1+1+1、1+1+2、2+2
     * 一共就3种方法，所以返回3
     */
    public class CoinsWaySameValueSamePapper {
        //根据题意要求，相同面值认为是同个货币 不能重复用 且只有一张 上面举例来说 只有货币1  2两种 1 四张 2 三张 组成4 两张1和一张2组成4 这里的1都是认为一样的 用其他两张1和其他2一起组合也是不可以的
        //所以我们需要先把arr数组转换下。 定义一个类,包含两个属性coins[] counts[]，将数组中货币面值和货币对应张数都分开提出来。再做递归或者动态规划
        public static class Info{
            public int[] coins;     //接收货币面值种类  [1,2]    1货币有4张  2货币有3张
            public int[] counts;    //接收货币面值张数  [4,3]
            public Info(int[] i, int[] j){
                coins = i;
                counts = j;
            }
        }
    
        //定义一个函数，将原函数arr数组 传入，转换返回Info类 拆分出货币值和张数值
        public static Info getInfo(int[] arr){
            //哈希表，用来保存 面值：张数
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int coin:arr){
                if(!map.containsKey(coin)){
                    map.put(coin,1);   //首次进入表中，就赋值1张
                }else {
                    map.put(coin,map.get(coin)+1);  //如果前面已经进入过表，那么张数就对应+1
                }
            }
    
            //哈希表填充完成后， 长度就是对应有多少个货币值  那么货币值数组和张数值数组肯定都是这个表的size大小 定义其两数组
            int n = map.size();
            int[] coins = new int[n];
            int[] counts = new int[n];
            int index = 0;             //数组遍历的索引赋值变量
            //遍历我们哈希表的货币值，张数值 填充对应的coins  counts数组中
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                coins[index] = entry.getKey();
                counts[index++] = entry.getValue();   //注意index++ 这里进行累加下标 不会影响前面货币值位置的赋值操作
            }
            return new Info(coins,counts);  //创建Info对象 一次将两数组返回
        }
    
    
        //方法一： 暴力递归
        //arr货币数组  目标值aim  返回能得到aim的货币选择方法数
        public static int coinsWay(int[] arr, int aim){
            //边界判断
            if(arr == null || arr.length == 0 || aim < 0) return 0;
            Info info = getInfo(arr);        //arr数组 转换货币面值数组coins和货币面值张数数组counts
            int[] coins = info.coins;
            int[] counts = info.counts;
    
            //传递货币面值数组，货币面值张数数组  索引从第一个值开始 得到aim目标值的全部方法数
           return process(coins, counts, 0, aim);
        }
    
        /**
         * 返回[index...]得到 rest剩余目标值的方法数
         * @param coins    货币面值数值数组
         * @param counts   货币面值张数数组
         * @param index    数组索引位置 从左开始往右
         * @param rest     目标值所剩余的值
         * @return
         */
        public static int process(int[] coins, int[] counts, int index, int rest){
            //base case  没有货币 index越界 如果前面rest剩余目标值为0了 说明是一种方法 返回1 否则就是0
            if(index == coins.length){
                return rest == 0? 1: 0;
            }
    
            //定义方法数
            int ways = 0;
    
            //分析情况，从左开始，可以选择的张数由counts决定 coins[0]货币张数是counts[0] 张数不能越界 并且coins[0]*张数不能大于rest剩余的目标值
            for(int count = 0; count <= counts[index] && count * coins[index] <= rest;count++){ //外层遍历的是每张货币的使用张数
                //方法数依次选择当前coins[index] count张数 然后index来到下个货币面值 rest剩余值要 减去 count张数 * coins[index]面值数
                ways += process(coins,counts,index+1,rest - count * coins[index]);
            }
            return ways;
        }
    
        //方法二： 动态规划
        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[] counts = info.counts;   //             货币张数数组
    
            //递归函数可变参数 index  范围在 0,coins.length    rest  范围 0,aim
            int n = coins.length;
            int[][] dp = new int[n+1][aim+1];
            dp[n][0] = 1;    //base case  没有货币 index越界 如果前面rest剩余目标值为0了 说明是一种方法 返回1 否则就是0
    
            //分析依赖 index货币 是依赖于 index+1货币 也就是 上一行依赖下一行  已知base case填充好了最后一行 所以可以从下往上推
            //从左开始，可以选择的张数由counts决定 coins[0]货币张数是counts[0] 张数不能越界 并且coins[0]*张数不能大于rest剩余的目标值
            for(int index = n-1; index >= 0; index--){   //倒数第二行开始往上遍历
                for(int rest = 0; rest <= aim; rest++){  //改行的每一列 从左往右
    
                    //定义方法数变量 累加
                    int ways = 0;
                    //每一个位置 依赖于 index+1下一行的 多个位置。 需要用for循环遍历 累加前面依赖的每个列值
                    for(int count = 0; count <= counts[index] &&  count * coins[index] <= rest; count++){
                        //依赖下一行， 列数是 当前剩余的目标值rest 减去使用了 对应当前行货币值conins[index]多种张数的情况
                        ways += dp[index+1][rest - count*coins[index]];
                    }
                    dp[index][rest] = ways;
                }
            }
            return dp[0][aim];   //根据递归主程序调用来看 是从0位置开始 目标值aim 返回dp数组对应的位置
        }
    
        //方法三： 动态规划  优化时间复杂度  方法二填充一个位置需要for循环，需要找规律平移成常数个的推算
        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[] counts = info.counts;   //             货币张数数组
    
            //递归函数可变参数 index  范围在 0,coins.length    rest  范围 0,aim
            int n = coins.length;
            int[][] dp = new int[n+1][aim+1];
            dp[n][0] = 1;    //base case  没有货币 index越界 如果前面rest剩余目标值为0了 说明是一种方法 返回1 否则就是0
    
            //分析依赖 index货币 是依赖于 index+1货币 也就是 上一行依赖下一行  已知base case填充好了最后一行 所以可以从下往上推
            //从左开始，可以选择的张数由counts决定 coins[0]货币张数是counts[0] 张数不能越界 并且coins[0]*张数不能大于rest剩余的目标值
            for(int index = n-1; index >= 0; index--){   //倒数第二行开始往上遍历
                for(int rest = 0; rest <= aim; rest++){  //改行的每一列 从左往右
    
                    //dp1赋值方式中我们假设一个例子 index = 3,rest=13 dp[3][13]  arr[3]=3; 也就是第4行第14列 arr[3]的货币值是3
                    //开始遍历 count =0 张时 ways = dp[4][13-0*3] = dp[4][13]  也就是第5行第14列 依赖下位置
                    //count =1 张时 way += dp[4][13-1*3] = dp[4][10]                第5行第11列 来到下位置的左边算3个位置
                    //count =2 张时 way += dp[4][13-2*3] = dp[4][7]                第5行第8列 来到下位置的左边算6个位置
                    //count =3 张时 way += dp[4][13-3*3] = dp[4][4]                第5行第8列 来到下位置的左边算9个位置
                    //count =4 张时 way += dp[4][13-4*3] = dp[4][1]                第5行第8列 来到下位置的左边算12个位置
                    //count =5 张时 way += dp[4][13-5*3] = dp[4][-2]               这里列数已经越界 所以不会遍历 不依赖
                    //这里可以得到确实依赖了有N个，那么我们就转换成常数个把！
                    //我们看看 index = 3,rest=10 dp[3][10] arr[3]同样也是货币值是3 因为对应index行数一样 行数代表的货币值。 这个位置就在dp[3][13]的左位置算货币值3个位置
                    //那么这个左位置dp[3][12] 怎么依赖，  同理 也是从count =0...一直到count = 3 dp[3][10 - 3*3] = dp[4][1],再往下就越界 并且这四张对应前面从count = 1 张往后的四个货币值
                    //由此规律可转换得到  dp[3][13] = dp[4][13] 下位置 +  dp[3][10] 左位置往arr[3]这个货币值的个数位置
                    //但是这里注意， 张数是有限张，这里假设 count只能3张
                    // 那么dp[3][13]依赖下一行dp[4][13]、dp[4][10] 、dp[4][7]、dp[4][4]
                    //     dp[3][10]依赖下一行           dp[4][10]、dp[4][7]、 dp[4][4]、dp[4][1] 比前面的多了一个dp[4][1]  前面不变依旧是少一个dp[4][13]
                    //需要判断  依赖的左位置 是否会多一个。
                    // 假设： count张数足够多到边界越界 那么就不存在这个多的一个
                    // 假设：rest剩余目标值 - (count+1)张 * conins[index] >=0  说明张数不够多，再往左增加一张货币值 剩余目标值还没小于0 那么表示dp[3][13] 依赖的dp[3][10] 左位置 是多加了一个dp[4][1] 那么就减掉就可以了
                    // 减去的位置是 [index+1][rest - (count+1)*coins[index]]
    
                    //先将依赖下位置的值赋值给当前位置
                    dp[index][rest] = dp[index+1][rest];
    
                    //依赖位置还是 左位置 rest-coins[index] 该列 先判断 该位置是否存在 边界溢出 如果没有小于0 就进行依赖传值
                   if(rest - coins[index] >= 0){
                       dp[index][rest] += dp[index][rest - coins[index]];
                   }
    
    
                    // 假设：rest剩余目标值 - (count+1)张 * conins[index] >=0  说明张数不够多，再往左增加一张货币值 剩余目标值还没小于0 那么表示dp[3][13] 依赖的dp[3][10] 左位置 是多加了一个dp[4][1] 那么就减掉
                    if(rest - (counts[index]+1)*coins[index] >= 0){
                        // 依赖左位置rest-coins[index]，但是多了一个值 下一行的 最左侧的位置 rest目标列- 当前货币值coins[index]*当前张数再多一张的位置counts[index]+1
                        dp[index][rest] -= dp[index+1][rest - (counts[index]+1)*coins[index]];
                    }
                }
            }
            return dp[0][aim];   //根据递归主程序调用来看 是从0位置开始 目标值aim 返回dp数组对应的位置
        }
    
        // 为了测试
        public static int[] randomArray(int maxLen, int maxValue) {
            int N = (int) (Math.random() * maxLen);
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = (int) (Math.random() * maxValue) + 1;
            }
            return arr;
        }
    
        // 为了测试
        public static void printArray(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // 为了测试
        public static void main(String[] args) {
            int maxLen = 10;
            int maxValue = 20;
            int testTime = 1000000;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr = randomArray(maxLen, maxValue);
                int aim = (int) (Math.random() * maxValue);
                int ans1 = coinsWay(arr, aim);
                int ans2 = dp1(arr, aim);
                int ans3 = dp2(arr, aim);
                if (ans1 != ans2 || ans1 != ans3) {
                    System.out.println("Oops!");
                    printArray(arr);
                    System.out.println(aim);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println(ans3);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }

### 五、Bob走棋盘概率 ###

> 给定5个参数，N，M，row，col，k  
> 表示在N\*M的区域上，醉汉Bob初始在(row,col)位置  
> Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位  
> 任何时候Bob只要离开N\*M的区域，就直接死亡  
> 返回k步之后，Bob还在N\*M的区域的概率

package class21;
    
    /**
     * 给定5个参数，N，M，row，col，k
     * 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
     * Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
     * 任何时候Bob只要离开N*M的区域，就直接死亡
     * 返回k步之后，Bob还在N*M的区域的概率
     */
    public class BobDie {
    
        //方法一： 暴力递归
        public static double livePosibility1(int row, int col, int k, int n, int m){
            //根据题意是求 走完K步还在N*M矩阵内的方法数 / 全部可走方法数种  概率值
            //递归函数是求 走K步后还在矩阵内的方法数   那么总共有多少种走法？
            //根据Bob每步等概率的上下左右 四个方向，每次走一个方向后，来到新位置后又可以走四个方向 然后继续还是可以走四个方向，直到走完K步
            //可以得到这个一个累乘的方法数 是 4^K 次  每次4个选择 一共K次 所以是4*4*4.. K次
            //概率我们返回一个浮点类型
            return (double) process(row,col,k,n,m) / Math.pow(4,k);
        }
        // 目前在row，col位置，还有rest步要走，走完了如果还在棋盘中就获得1个生存点，返回总的生存点数
        //当前还有rest步 不走出n*m的方法数 因为方法数是4^k，比较大，假设矩阵很大，那么int类型可能不够 所以我们就用Long类型
        public static long process(int row, int col, int rest, int N, int M) {
            //base case: 当前位置越界 那么就说明死亡 返回0种
            if (row < 0 || row == N || col < 0 || col == M) {
                return 0;
            }
            //base case: 没有走前面判断 表示没有越界  如果步数走完到0 就返回1
            if (rest == 0) {
                return 1;
            }
            // 还在棋盘中！还有步数要走
            // 分析情况 可以走四个方向  上下左右 每次步数同步少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;
        }
    
    
    
        //方法二： 动态规划
        public static double livePosibility2(int row, int col, int k, int n, int m){
            //判断递归的可变参数 有 row,col,k 那么我们就定义一个三维数组 递归过程达到的有效范围是 0,n-1  0,m-1  0,k
            long[][][] dp = new long[n][m][k+1];
            //初始化 结合递归的base case 第0层k=0 表示0k 所在的行列范围时0,n-1  o,m-1的位置不越界属于是方法数可达 赋值1
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    dp[i][j][0] = 1;
                }
            }
    
            //分析依赖 剩余步数k 依赖 k-1 也就是上层依赖下层 已知我们把最底层已经填充好 依次从上往下填充即可
            //前面0层填好 接着就1...
            for(int rest = 1; rest <= k; rest++){ //第三维 步数
                for(int r = 0; r < n;r++){          // 二维的 行数
                    for(int c = 0; c < m;c++){    // 二维的 列数
                        //根据递归，步方向依赖 上下左右四个位置的值 那么就调用pick函数直接得到该位置值，因为会存在越界情况 所以我们单独写个函数比较合适
                        dp[r][c][rest] = pick(dp, r-1, c, n, m, rest-1);  //上r-1 步数-1 依赖下层
                        dp[r][c][rest] += pick(dp, r+1, c, n, m, rest-1);
                        dp[r][c][rest] += pick(dp, r, c-1, n, m, rest-1);
                        dp[r][c][rest] += pick(dp, r, c+1, n, m, rest-1);
    
                    }
                }
            }
            return (double) dp[row][col][k] / Math.pow(4,k);  //根据主函数调用递归 是人所在行列 k步
        }
    
        //定义一个函数 传递三维数组dp 获得对应层rest的 行row 列col 具体位置 n*m的矩阵
        public static long pick(long[][][] dp, int row,int col, int n, int m, int rest ){
            if(row < 0 || row == n || col < 0 || col == m) return 0;//越界矩阵的 肯定都是0 不管rest在第几层
            return dp[row][col][rest];
        }
    
        public static void main(String[] args) {
            System.out.println(livePosibility1(6, 6, 10, 50, 50));
            System.out.println(livePosibility2(6, 6, 10, 50, 50));
        }
    }

### 六、688. 骑士在棋盘上的概率 ###

[LeetCode 668.骑士棋盘上的概率][LeetCode 668.]

![a0c70bb7c865e8d2623a4d71e82ca1ae.png][]

![f4ccdd018a5609baa317c38d1e13e973.png][]

package class21;
    
    /**
     *
     * https://leetcode.cn/problems/knight-probability-in-chessboard/
     * 在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
     *
     * 象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
     * 每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
     *
     * 骑士继续移动，直到它走了 k 步或离开了棋盘。
     *
     * 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。
     * 输入: n = 3, k = 2, row = 0, column = 0
     * 输出: 0.0625
     * 解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
     * 在每一个位置上，也有两种移动可以让骑士留在棋盘上。
     * 骑士留在棋盘上的总概率是0.0625。
     */
    public class knightProbability {
    
        //方法一：暴力递归
        public double knightProbability1(int n, int k, int row, int column) {
            //调用递归函数
            return process(n,k,row,column);
        }
    
        /**
         * 在矩阵n*n中，骑士在[r,c]位置时 还剩rest步走完全部方法后 返回骑士还在矩阵中的概率
         * @param n    棋盘n行n列
         * @param rest  剩余步数
         * @param r    当前行位置
         * @param c    当前列位置
         * @return     走完后还在棋盘的概率
         */
        public double process(int n, int rest, int r, int c){
            //base case: 如果越界 说明不在棋盘了 返回0 注意这个走位 越界是可能回大于n的
            if(r <0 || r >= n || c < 0 || c >= n) return 0;
            //base case: 不越界 并且步数走完了 说明骑士最终还在棋盘内 返回1
            if(rest == 0){
                return 1;
            }
    
            //分析常规情况 依次时依赖8个方向,每走一步就是1/8概率，走两步就是1/8 * 1/8的概率 也就是64种走法
            double ans = 0;
            //依赖八个方向 分别将八个方向的概率都进行累加
            ans += (process(n,rest-1,r-2,c+1)/8) ;
    
            ans += (process(n,rest-1,r-1,c+2)/8) ;
    
            ans += (process(n,rest-1, r+1, c+2)/8);
    
            ans += (process(n,rest-1,r+2,c+1)/8);
    
            ans += (process(n,rest-1,r+2,c-1)/8) ;
    
            ans += (process(n,rest-1,r+1,c-2)/8);
    
            ans += (process(n,rest-1, r-1, c-2)/8);
    
            ans += (process(n,rest-1,r-2,c-1)/8);
    
            return ans;
        }
    
    
        // 方法二、改的记忆化搜索版本   记忆化搜索 就是从顶到底的动态规划
        //记忆化搜索，先从大状态开始，缺什么小状态就去调用，一个状态算过了，就记录缓存里。下次再调用，直接返回。
    
        public double knightProbability2(int n, int k, int row, int column) {
            double[][][] dp = new double[n][n][k + 1];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int t = 0; t <= k; t++) {
                        dp[i][j][t] = -1;
                    }
                }
            }
            return process2(n, k, row, column, dp);
        }
    
        public double process2(int n, int rest, int r, int c, double[][][] dp) {
            if (r < 0 || r >= n || c < 0 || c >= n) {
                return 0;
            }
            if (dp[r][c][rest] != -1) {
                return dp[r][c][rest];
            }
            double ans = 0;
            if (rest == 0) {
                ans = 1;
            } else {
                ans += (process2(n, rest - 1, r - 2, c + 1, dp) / 8);
                ans += (process2(n, rest - 1, r - 1, c + 2, dp) / 8);
                ans += (process2(n, rest - 1, r + 1, c + 2, dp) / 8);
                ans += (process2(n, rest - 1, r + 2, c + 1, dp) / 8);
                ans += (process2(n, rest - 1, r + 2, c - 1, dp) / 8);
                ans += (process2(n, rest - 1, r + 1, c - 2, dp) / 8);
                ans += (process2(n, rest - 1, r - 1, c - 2, dp) / 8);
                ans += (process2(n, rest - 1, r - 2, c - 1, dp) / 8);
            }
            dp[r][c][rest] = ans;
            return ans;
        }
    
    
        //方法三：动态规划  从底到顶的动态规划
        //先从小状态开始，把小状态都算完，才去算大状态。保证每个大状态都不缺少依赖了，才会来到大状态的格子去算
        
        public static double dp(int n, int k, int row, int column){
            //根据递归函数知道又三个变量 ，定义一个三维数组  递归调用入参 返回dp[row][column][k] 有效范围就是 0,n-1   0,n-1  0,k+1
            //因为每个值是概率 那么数组就要定义double类型
            double[][][] dp = new double[n][n][k+1];
    
            //根据递归base case   row column行列 不越界且步数位0 也就是第0层 那么值就为1
            for(int r = 0; r < n; r++){
                for(int c = 0; c < n; c++){
                    dp[r][c][0] = 1;
                }
            }
    
            //分析递归依赖 的八个方向 rest 步数都是依赖于rest-1层 1层依赖0层 2层依赖1层 目前初始化了0层了 所以从下往上填充 从1层开始
            for(int rest = 1; rest <= k; rest++){
                for(int r = 0; r < n; r++){
                    for(int c = 0; c < n; c++){
                        dp[r][c][rest] += pick(dp,n,rest-1,r-2,c+1)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r-1,c+2)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r+1,c+2)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r+2,c+1)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r+2,c-1)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r+1,c-2)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r-1,c-2)/8;
                        dp[r][c][rest] += pick(dp,n,rest-1,r-2,c-1)/8;
                    }
                }
            }
            return dp[row][column][k];
        }
    
        //获取每一层rest的 二维数组位置c,r 值
        public static double pick(double[][][]dp, int n, int rest, int r, int c){
            //如果越界 说明不在棋盘了 返回0 注意这个走位 越界是可能回大于n的
            if(r < 0 || r >= n || c < 0 || c >= n) return 0;
            return dp[r][c][rest];
        }
    
    }

### 七、记忆化搜索和动态规划 ###

> 记忆化搜索，也叫：从顶到底的动态规划  
> 记忆化搜索，先从大状态开始，缺什么小状态就去调用，一个状态算过了，就记录缓存里。下次再调用，直接返回。  
>   
> dp动态规划又叫：从底到顶的动态规划  
> dp，先从小状态开始，把小状态都算完，才去算大状态。保证每个大状态都不缺少依赖了，才会来到大状态的格子去算

> 如果递归在计算过程中，  
> 1.每个位置 依赖的行为是有限个数，那么递归版本优化成记忆化搜索 后，就跟dp动态规划的时间复杂度是一样的了。 有多少个小状态数量要计算 就是多少复杂度   
> 2.如果依赖的是枚举行为，那么时间复杂度就是 状态数量\*枚举量  
> 3.如果是枚举 时间复杂度还可优化， 比如货币问题中，原先依赖是下一个的多个位置 根据邻近位置计算转换成 只要左边位置和下边位置的有限个数数量依赖，此时优化之后时间复杂度也就跟dp是一样的了 多少状态数量就是多少时间复杂度

[LeetCode 668.]: https://leetcode.cn/problems/knight-probability-in-chessboard/description/
[a0c70bb7c865e8d2623a4d71e82ca1ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/fa0c1dc869704eb18fcbc8c774d19122.png
[f4ccdd018a5609baa317c38d1e13e973.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/32d4898df2a14ef0926d9c3d3e655940.png