【数据结构与算法之面试题】递归和动态规划系列面试题

迷南。 2024-03-25 23:54 93阅读 0赞

#### 【数据结构与算法之面试题】递归和动态规划系列面试题 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之面试题】递归和动态规划系列面试题
         *   *   *  1 分解质因数
                 *  2 拨号盘字母组合
                 *  3 组合的总和
                 *  4 在大矩阵中找k
                 *  5 跳跃游戏
                 *  6 机器人的最小路径长度
                 *  7 聪明的侦探

###### 1 分解质因数 ######

【题目描述】任何一个合数都可以写成几个质数相乘的形式，这几个质数叫作这个合数的质因数，例如 24 = 2 x 2 x 2 x 3。把一个合数写成几个质数相乘的形式叫作分解质因数。

一个质数的质因数本身是它本身。编写一个程序实现分解质因数。

*  质数：除了1和它本身再没有其他因数的数字，例如2、3、5、7等
 *  合数：除了1和它本身还存在其他因数的数字，例如24 的因数除了1和24 还有2，把24分解质因数为 24 = 2 x 2 x 2 x 3，其中每个因数(2、2、2、3) 都是质数。

对整数n 分解质因数时，如果n 本身是质数，则直接返回n，不需要分解。如果n 是合数，则从2 到 n -1顺序地查找 n 的因数，第1个找到的因数 i 一定是质因数。例如24 = 2 x 12，2是找到的第1个24的因数，也是质因数。

接下来继续对 n / i 分解质因数，很明显，这就是一个递归调用过程了。

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DecompositionPrimeFactor
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 19:34
     */
    
    public class DecompositionPrimeFactor {
        
    
        public static void getPrimeFactor(int n) {
        
    
            int i;
            if (isPrime(n)) {
        
                System.out.print(n + " ");  // n是质数, 直接返回
            } else {
        
                for (i = 2; i <= n - 1; i++) {
        
                    if (n % i == 0) {
        
                        System.out.print(i + " ");
                        getPrimeFactor(n / i);
                        break;
                    }
                }
            }
        }
    
        private static boolean isPrime(int n) {
        
            if (n == 1 || n == 2) {
        
                return true;
            }
            for (int i = 2; i < n; i++) {
        
                if (n % i == 0) {
        
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
        
    
            getPrimeFactor(1155);
            System.out.println();
            getPrimeFactor(1024);
            System.out.println();
            getPrimeFactor(210);
    
        }
    
    }

运行结果

![在这里插入图片描述][0b4551292e964de18ba2b14bac7f213d.png_pic_center]

###### 2 拨号盘字母组合 ######

【题目描述】在手机的拨号盘中，每一个数字按键(除 1外) 都对应着一组英文字母。

如下：

![在这里插入图片描述][1f5e083448ff45b681a4afdcdc08b05d.png_pic_center]

现给定一个数字字串，要求返回所有可能的字符串组合。

例如：给定数字字串23，输出\[ad，ae，af、bd、be、bf、cd、ce、cf\]

，

如何找出所有的组合，最直观的方法是利用一个多重循环将每一组字母序列中的字母进行组合，最终可穷举出全部的组合。但是这样子的代码缺乏灵活性，如果数字字串包含n 个数字，则需要对应一个n 重循环来完成穷举操作。

其实这是一个很明显的自上而下的递归问题，直接解答吧。

Java 实现：

import java.util.HashMap;
    import java.util.HashSet;
    import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: LetterCombinations
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 19:49
     */
    
    public class LetterCombinations {
        
    
        public static HashMap<Integer, String> phoneNumbers = new HashMap<Integer, String>();
    	// 存放拨号盘上数字和字母列表的对应关系
        static {
        
            phoneNumbers.put(2, "ABC");
            phoneNumbers.put(3, "DEF");
            phoneNumbers.put(4, "GHI");
            phoneNumbers.put(5, "JKL");
            phoneNumbers.put(6, "MNO");
            phoneNumbers.put(7, "PQRS");
            phoneNumbers.put(8, "TUV");
            phoneNumbers.put(9, "WXYZ");
        }
    
        public static void getLetterCombinations(int[] numbers) {
         // 获取numbers中每个数字对应字母的所有组合，并将这些字母组合打印
            
            Stack<Character> stack = new Stack<Character>(); // 存放字母组合
            getLetterCombinations(numbers, stack);
        }
    
        public static void getLetterCombinations(int[] numbers, Stack<Character> stack) {
         // 查找字母组合
    
            if (numbers.length == 1) {
        
                String characters = phoneNumbers.get(numbers[0]);
                for (int i = 0; i < characters.length(); i++) {
        
                    stack.push(characters.charAt(i));
                    System.out.println(stack);
                    stack.pop();
                }
                return;
            }
    
            String characters = phoneNumbers.get(numbers[0]); // 以numbers中的第1个数字作为开头对组合进行分类
            int[] tmp = new int[numbers.length - 1];
            System.arraycopy(numbers, 1, tmp, 0, numbers.length - 1);
    
            for (int i = 0; i < characters.length(); i++) {
        
                stack.push(characters.charAt(i));
                getLetterCombinations(tmp, stack);
                stack.pop();
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] numbers = {
        2, 3};
            getLetterCombinations(numbers);
    
        }
    
    }

运行结果

![在这里插入图片描述][d210bc29891b4ae39abb215e4dd2c42f.png_pic_center]

###### 3 组合的总和 ######

【题目描述】给定一个无重复元素的数组 candidates 和一个目标数 target，找出candidates 中所有可以使数字之和为target 的组合。candidates 中的数字可以无限次被选取。

举个栗子：

【输入】candidates = \{2,3,6,7\}，target = 7

【输出】\{7\}、\{2,2,3\}

【输入】candidates = \{2,3,5\}，target = 8

【输出】\{2,2,2,2\}，\{2,3,3\}，\{3,5\}

其实也可以比较容易想到用递归方法进行求解

要得到 candidates中某些元素的组合，并使得每个组合中的元素之和等于给定的target，可以将问题拆分成两个小问题：

1.  组合中包含元素candidates\[0\]，从而可以得到一系列组合
2.  组合中不包含元素candidates\[0\]，从而又可以得到一系列组合。

写成递归表达式：

getCombine(candidates\[0…n\] ， target) =

*  \{candidates\[0\] ， getCombine(candidates\[1…n\]，target - candidates\[0\])\}
 *  \{getCombine(candidates\[1…n\]，target\}

但是这样没有满足到某个数可以无限次选择的条件，

所以表达式还要稍微修改一下

getCombine(candidates\[0…n\] ， target) =

*  \{candidates\[0\]…candidates\[0\] 【这里表示可以包含1个或多个candidates\[0\]】 ， getCombine(candidates\[1…n\]，target - i \* candidates\[0\])\} ( i 代表candidates\[0\] 的个数)
 *  \{getCombine(candidates\[1…n\]，target\}

Java 实现：

import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SummationOfCombinations
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 20:25
     */
    
    public class SummationOfCombinations {
        
    
        public static void getCombine(int[] candidates, int target, Stack<Integer> stack) {
        
    		 // stack的作用是暂存得到的组合，并打印
            
            int[] tmp;
            if (candidates[0] == target) {
        
                // 如果candidates[0]恰好等于target, 则找到一个答案
                stack.push(candidates[0]);
                System.out.println(stack);
                stack.pop();
    
                if (candidates.length > 1) {
         //在candidates[0] 后面的子数组中递归寻找元素之和为target的组合
                    tmp = new int[candidates.length - 1];
                    System.arraycopy(candidates, 1, tmp, 0, candidates.length - 1);
                    getCombine(tmp, target, stack);
                }
    
            } else if (candidates[0] > target) {
        
                // 已经大于了就不能选candidates[0] 了，直接越过candidates[0]，在后面的子数组中递归寻找
                if (candidates.length > 1) {
        
                    tmp = new int[candidates.length - 1];
                    System.arraycopy(candidates, 1, tmp, 0, candidates.length - 1);
                    getCombine(tmp, target, stack);
                }
                
            } else {
         // 来到这儿说明candidates[0] < target 
                
                if (candidates.length > 1) {
         
                    int i, j; // 选candidates[0]
                    for (i = 1; i * candidates[0] <= target; i++) {
        
                        stack.push(candidates[0]);
                        if (i * candidates[0] == target) {
        
                            System.out.println(stack);
                        } else {
        
                            tmp = new int[candidates.length - 1];
                            System.arraycopy(candidates, 1, tmp, 0, candidates.length - 1);
                            getCombine(tmp, target - i * candidates[0], stack);
                        }
                    }
    
                    // 不选candidates[0]
                    for (j = 0; j < i - 1; j++) {
        
                        stack.pop();
                    }
                    tmp = new int[candidates.length - 1];
                    System.arraycopy(candidates, 1, tmp, 0, candidates.length - 1);
                    getCombine(tmp, target, stack);
                }
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        2, 3, 5};
            Stack<Integer> stack = new Stack<Integer>();
            getCombine(array, 8, stack);
    
        }
    
    }

运行结果

![在这里插入图片描述][351e17f7544e44a2967853743546cb0d.png_pic_center]

###### 4 在大矩阵中找k ######

【题目描述】有一个m x n 阶的整数矩阵，m 和 n 可以是任意值。矩阵的每一行都按值严格递增，矩阵的每一列也按值严格递增，矩阵中没有重复的数字。现输入一个整数k，要求在该矩阵中查找是否存在k，如果存在则指出k 在矩阵中的位置，否则提示没找到。要求复杂度尽可能小。

其实这个矩阵会很有意思，

![在这里插入图片描述][6f0662e36f5744b189e8bbe7e4d4f2f3.png_pic_center]

这样的矩阵中的任何子矩阵都满足左上角的元素最小，右下角的元素最大。

所以在查找元素k 时，如果k 小于某个子矩阵的左上角的元素时，那么这个子矩阵中绝对没有k，同理如果k 大于每个子矩阵的右下角元素，那么这个子矩阵也不会有k。

【查找思路】

给定k 值后，沿着矩阵对角线元素进行比较，如果恰好找到一个对角线上的元素 = k，则查找成功直接返回，否则k在某两个对角线元素之间。

举个栗子，在下面这个矩阵中查找元素8，将8 与矩阵的对角线元素进行比较，

![在这里插入图片描述][566d67070129458fb1bfb01476492464.png_pic_center]

由于8 ＜ 11，同时 8 ＞ 6，因此左上角的矩阵与右下角的矩阵就都可以从查找范围内排除了。然后在右上角和左下角的矩阵中按照同样的方法从对角线开始进行查找。

但是这样子只考虑了方阵的情况，即矩阵中存在对角线，题目中并没有说矩阵是方阵，假设我们查找的元素是4 而不是8，

![在这里插入图片描述][ddc9162b1d7048d39cf011e4c2a26b5b.png_pic_center]

这样左下角和右上角就不对劲了 ，所以我们的算法中还要考虑到列数大于行数以及行数大于列数的情况。

*  对于列数大于行数的矩阵，如果k 大于矩阵p\[i\]\[j\] (i = j = 0,1,2,3…)中的任何元素，那么下一步的查找范围就是下面这样的 。
    
    ![在这里插入图片描述][87232ee0295c439ea0f293bd0c9b3471.png_pic_center]
 *  对于行数大于列数的矩阵，如果k 大于矩阵p\[i\]\[j\] (i = j = 0,1,2,3…)中的任何元素，那么下一步的查找范围就是下面这样的 。
    
    ![在这里插入图片描述][27b655e162b64b198d35a1286e09d245.png_pic_center]

所以综合一下：

在将k 与p\[i\]\[j\] (i = j = 0,1,2,3，…) 进行比较时，分下面几种情况进行考虑：

1.  如果k 小于矩阵左上角的元素，则表明该矩阵中不含有元素k，返回
2.  如果在p\[i\]\[j\] 上查找到k，则返回成功
3.  如果k 位于两个p\[i\]\[j\] 之间，则在右上角和左下角两个矩阵中继续查找
4.  如果k 大于p\[i\]\[j\] 上的任何元素，则分是方阵和不是方阵两种情况考虑。

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: FindKInTheBigMatrix
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 21:13
     */
    
    class Location {
        
        int row;
        int column;
    
        public Location(int row, int column) {
        
            this.row = row;
            this.column = column;
        }
    }
    
    public class FindKInTheBigMatrix {
        
    
        int[][] p;
    
        /**
         * @param i 当前搜索的矩阵的左上角元素的行号
         * @param j 当前搜索的矩阵的左上角元素的列号
         * @param s 当前搜索的矩阵的右下角元素的行号
         * @param t 当前搜索的矩阵的右下角元素的列号
         * @param k 查找元素值
         * @return
         */
        public Location searchK(int i, int j, int s, int t, int k) {
        
            Location position;
    
            int i_tmp = i, j_tmp = j;
    
            for (i_tmp = i, j_tmp = j; i_tmp <= s && j_tmp <= t; i_tmp++, j_tmp++) {
        
                // 沿着对角线搜索
                if (p[i_tmp][j_tmp] == k) {
        
                    // 在对角线上找到了
                    return new Location(i_tmp, j_tmp);
                } else if (k < p[i_tmp][j_tmp]) {
        
                    if (i_tmp > i && j_tmp > j && i_tmp <= s && j_tmp <= t) {
        
                        // k 位于两个p[i][j]之间
                        if ((position = searchK(i, j_tmp, i_tmp - 1, t, k)) != null) {
        
                            return position;
                        }
                        if ((position = searchK(i_tmp, j, s, j_tmp - 1, k)) != null) {
        
                            return position;
                        }
    
                        return null;
                    } else {
        
                        return null;
                    }
                }
            }
    
            // k 大于对角线上的任何值, 分两种情况讨论
            if (j_tmp > t && i_tmp <= s) {
         // 行大于列的矩阵
                if ((position = searchK(i_tmp, j, s, t, k)) != null) {
        
                    return position;
                }
            } else if (i_tmp > s && j_tmp <= t) {
         // 行小于列的矩阵
                if ((position = searchK(i, j_tmp, s, t, k)) != null) {
        
                    return position;
                }
            }
    
            return null;
        }
    
        public static void main(String[] args) {
        
    
            FindKInTheBigMatrix findKInTheBigMatrix = new FindKInTheBigMatrix();
            int[][] p = {
        
                    {
        1, 2, 3, 16, 20},
                    {
        5, 8, 9, 17, 21},
                    {
        6, 11, 12, 18, 22},
                    {
        7, 14, 15, 19, 23}
            };
    
            findKInTheBigMatrix.p = p;
            Location location = findKInTheBigMatrix.searchK(0, 0, 3, 4, 19);
            System.out.println(location.row + " " + location.column);
    
            Location location1 = findKInTheBigMatrix.searchK(0, 0, 3, 4, 55);
            System.out.println(location1);
    
        }
    }

运行结果

![在这里插入图片描述][8b361de1efff4e32a1349c8dc3cf5247.png_pic_center]

没问题。

###### 5 跳跃游戏 ######

【题目描述】给定一个非负整数数组，你位于数组的第1个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数达到数组的最后一个位置，计算出最少的跳跃次数。

【举个栗子】给定数组\{2,3,1,1,4\}，输出2.

【解释】第1次从下标为0的位置跳到下标为1的位置(最大跳跃长度为2，但是只跳1个长度)，第2次跳跃从下标为1的位置跳到下标为4的位置(最大跳跃长度为3，实际也跳了3)，刚好到达数组最后一个位置。

递归求法

给定这个数组array，起点在array\[0\]，假设array\[0\] 的值为n，可以按照下面的方法计算出跳跃到数组尾部的最少次数：

*  先跳跃1步的情况，从array\[0\] 跳1 步到array\[1\]，然后以array\[1\] 为新起点计算到数组尾部最少的跳跃次数，记作 k 1 k\_1 k1，最终得到的最少跳跃次数为  k 1 + 1 k\_1 + 1 k1\+1
 *  先跳跃2步的情况，从array\[0\] 跳2 步到array\[2\]，然后以array\[2\] 为新起点计算到数组尾部最少的跳跃次数，记作 k 2 k\_2 k2，最终得到的最少跳跃次数为  k 2 + 1 k\_2 + 1 k2\+1
 *  …
 *  先跳跃n步的情况，从array\[0\] 跳n步到array\[n\]，然后以array\[n\] 为新起点计算到数组尾部最少的跳跃次数，记作 k n k\_n kn，最终得到的最少跳跃次数为  k n + 1 k\_n + 1 kn\+1

从 k 1 + 1 k\_1 + 1 k1\+1、  k 2 + 1 k\_2 + 1 k2\+1、…、  k n + 1 k\_n + 1 kn\+1 中选取最小值，就是答案。

设F(i) 表示以数组元素array\[i\] 为起点，到数组尾部的最少跳跃次数，n 为array\[i\] 的值，t 为数组array 最后一个元素的下标，则F(i) 可以表示为下面这样的递归函数：

F(i) =

*  当i <t 时，F(i) = min(1 + F(i + 1) , 1 + F(i + 2) + … + 1 + F(i + n))
 *  当i ≥ t 时，F(i) = 0

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: JumpingGame
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 10:18
     */
    
    public class JumpingGame {
        
    
        public static int jumpGame(int[] array) {
        
            return jump(0, array);
        }
    
        private static int jump(int index, int[] array) {
        
            int min = 10000;
    
            if (index >= array.length - 1) {
        
                return 0;
            }
            for (int i = 1; i <= array[index]; i++) {
        
                int steps = 1 + jump(index + i, array);
                if (min > steps) {
        
                    min = steps;
                }
            }
    
            return min;
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        2, 3, 1, 1, 4};
            System.out.println(jumpGame(array));
        }
    
    }

运行结果

![在这里插入图片描述][cd1d87998b7b423ba042ef7ae186ba2e.png_pic_center]

递归算法虽然容易理解，但是缺点也很明显，就是存在大量的冗余计算，以上面的例子来说，计算F(0) 时，因为array\[0\] = 2，所以F(0) = min(1 + F(1) , 1 + F(2))，又因为array\[1\] = 3，所以F(1) = min(1 + F(2) , 1 + F(3) , 1 + F(4))，F(2) 就会被计算两次。

其实我们还可以使用动态规划来求解这个题，自底向上，从F(k) 【k是数组尾部元素的下标】开始逐步向前计算，最终求出F(0)。

【演示动态规划求解过程】

给定的数组为array\[5\] = \{2,3,1,1,4\}，5个元素，对应下标为 0 - 4.

计算F(4)，即以数组的最后一个元素为起点跳到数组尾部的最少跳跃次数，很明显是0

计算F(3)，因为array\[3\] = 1,代表从array\[3\] 开始最多只能跳1步，而从 array\[3\] 到 array\[4\] 刚好也只需要1步，所以F(3) = 1

计算F(2)，因为array\[2\] = 1,代表从array\[2\] 开始最多只能跳1步到达array\[3\] ，array\[3\] 到 array\[4\] 要F(3) = 1步，所以F(2) = 1 + 1= 2

计算F(1)，因为array\[1\] = 3,代表从array\[1\] 开始最多能跳3步

*  跳1步，从array\[1\] 到 array\[2\] ，得到最小跳跃次数为 1 + F(2) =1 + 2 =3
 *  跳2步，从array\[1\] 到 array\[3\]，得到最小跳跃次数为1 + F(3) = 1 + 1 = 2
 *  跳3步，直接从array\[1\] 到了 array\[4\]，得到最小跳跃数为 1 + F(4) = 1 + 0 = 1

所以F(1) = min(3, 2, 1) = 1

计算F(0)，因为array\[0\] = 2,代表从array\[0\] 开始最多能跳2步

*  跳1步，从array\[0\] 到 array\[1\] ，得到最小跳跃次数为 1 + F(1) =1 + 1 =2
 *  跳2步，从array\[0\] 到 array\[2\]，得到最小跳跃次数为1 + F(2) = 1 + 2 = 3

所以F(0) = min(3, 2) = 2.

答案就出来了。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: JumpingGamev2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 10:35
     */
    
    public class JumpingGamev2 {
        
    
        public static int jumpGame(int[] array) {
        
            int len = array.length;
    
            int[] tmp = new int[len]; // tmp 用于保存F(4), F(3)...,F(0)
            int min = 1000;
    
            tmp[len - 1] = 0; // F(4) = 0
            for (int i = len - 2; i >= 0; i--) {
        
                for (int j = 1; j <= array[i]; j++) {
        
                    if (i + j <= len - 1 && min > tmp[i + j] + 1) {
        
                        min = tmp[i + j] + 1;
                    }
                }
    
                tmp[i] = min;
                min = 1000;  // 还原现场
            }
    
            return tmp[0];
    
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        2, 3, 1, 1, 4};
            System.out.println(jumpGame(array));
    
        }
    
    }

运行结果

![在这里插入图片描述][f38c045b383543f78e150e376f40afe9.png_pic_center]

没问题。

###### 6 机器人的最小路径长度 ######

【题目描述】给定一个包含非负整数的m x n的网格，机器人位于该网格的左上角，已知机器人每次只能向右走一步或者向下走一步，问该机器人从网格的左上角走到网格的右下角，最小路径长度为多少。

举个栗子：

假设给定的网格如下：

![在这里插入图片描述][d3c1a17997504deb9db5b148bf6ff6a0.png_pic_center]

所以从左上角走到右下角的最小路径长度为1 + 0 + 2 + 5 + 2 = 10，路径为 1 → 0 → 2 → 5 → 2 。

同样我们用两种方法来思考：

递归实现

自顶向下思考这个问题

![在这里插入图片描述][119b7abe6bd24489a4dd690700b1faac.png_pic_center]

*  绿色规模问题，求出(starti + 1, startj) 到 (endi , endj) 的最小路径长度
 *  紫色规模问题，求出(starti, startj + 1) 到 (endi , endj) 的最小路径长度

取两者的较小值 再加上 (starti , startj) 的值，即为答案。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: 机器人的最小路径长度
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 11:02
     */
    
    public class TheMinimumPathLengthOfTheRobot {
        
    
        public static int getMinPathsSum(int[][] net, int starti, int startj, int endi, int endj) {
        
    
            if (starti == endi - 1 && startj == endj) {
        
                return net[starti][startj] + net[endi][endj];
            }
    
            if (starti == endi && startj == endj - 1) {
        
                return net[starti][startj] + net[endi][endj];
            }
    
            if (starti > endi || startj > endj) {
        
                return -1;
            }
    
            int path1 = getMinPathsSum(net, starti + 1, startj, endi, endj);
            int path2 = getMinPathsSum(net, starti, startj + 1, endi, endj);
    
            if (path1 < 0) {
        
                return net[starti][startj] + path2;
            } else if (path2 < 0) {
        
                return net[starti][startj] + path1;
            } else if (path1 < path2) {
        
                return net[starti][startj] + path1;
            } else {
        
                return net[starti][startj] + path2;
            }
        }
    
        public static void main(String[] args) {
        
    
            int[][] net = {
        
                    {
        1, 3, 1, 5, 2, 6},
                    {
        0, 2, 3, 1, 4, 9},
                    {
        9, 5, 7, 1, 2, 3},
                    {
        8, 0, 2, 3, 1, 3},
                    {
        0, 3, 5, 1, 5, 3},
                    {
        0, 2, 5, 2, 1, 1}
            };
    
            System.out.println(getMinPathsSum(net, 0, 0, 5, 5));
    
        }
    
    }

运行结果

![在这里插入图片描述][798ee1148bb948ccaa43f88c15a02f34.png_pic_center]

这是递归方式，还是那个问题，重复调用递归函数，会产生大量的重复计算。

所以自底向上来了

我们可以利用一个与原网格同样大小的矩阵matrix，规定该矩阵上每个位置的值 = 网格中对应位置上的点到达终点(endi , endj) 的最小路径长度，这样递归关系就可以转换为

matrix\[i\]\[j\] = net\[i\]\[j\] + min(matrix\[i - 1\]\[j\] , matrix\[i\]\[j - 1\])，这就是这个问题的状态转移方程。

而且在网格中，最后一行只能往右走，最后一列只能往下走，可以利用这两个特点初始化矩阵的最后一行和最后一列。像下面这样

![在这里插入图片描述][c2091ffc3226401187f718621448a6fa.png_pic_center]

接着按照状态转移公式，把这个矩阵填满。

![在这里插入图片描述][535df1bd02214c77b8c125962c49fa06.png_pic_center]

最终得到的matrix\[0\]\[0\] 就是我们要的答案。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: TheMinimumPathLengthOfTheRobotV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 12:34
     */
    
    public class TheMinimumPathLengthOfTheRobotV2 {
        
    
        public static int getMinPathsSum(int net[][], int endi, int endj) {
        
    
            int[][] matrix = new int[endi + 1][endj + 1];
            int i, j;
    
            // 初始化matrix 右下角元素
            matrix[endi][endj] = net[endi][endj];
    
            // 初始化matrix 最后一行
            for (i = endi, j = endj - 1; j >= 0; j--) {
        
                matrix[i][j] = net[i][j] + matrix[i][j + 1];
            }
    
            // 初始化matrix 最后一列
            for (i = endi - 1, j = endj; i >= 0; i--) {
        
                matrix[i][j] = net[i][j] + matrix[i + 1][j];
            }
    
            // 通过matrix的最后一行和最后一列生成整个矩阵
            for (j = endj - 1; j >= 0; j--) {
        
                for (i = endi - 1; i >= 0; i--) {
        
                    matrix[i][j] = net[i][j] + Math.min(matrix[i + 1][j], matrix[i][j + 1]);
                }
            }
    
            return matrix[0][0];
        }
    
        public static void main(String[] args) {
        
    
            int[][] net = {
        
                    {
        1, 3, 1, 5, 2, 6},
                    {
        0, 2, 3, 1, 4, 9},
                    {
        9, 5, 7, 1, 2, 3},
                    {
        8, 0, 2, 3, 1, 3},
                    {
        0, 3, 5, 1, 5, 3},
                    {
        0, 2, 5, 2, 1, 1}
            };
    
            System.out.println(getMinPathsSum(net, 5, 5));
    
        }
    
    }

运行结果

![在这里插入图片描述][7993f030547144e6a2ff3779b2d6376e.png_pic_center]

没问题。

###### 7 聪明的侦探 ######

【题目描述】一个职业小偷计划盗窃沿街的房屋，小偷提前摸清了每个房屋中现金的数额，如下

![在这里插入图片描述][980ca5f43e9e421b9f3ef2210b511231.png_pic_center]

已知相邻的房屋装有连通的报警装置，如果盗窃了相邻的房屋，报警装置就会发出警报。所以小偷不能盗窃相邻的房屋，同时又要尽可能多的盗窃现金。狡猾的小偷研究许久终于找到一个盗窃的方案，并实施了盗窃。

现在警察要侦破这起盗窃案，首先要确定盗窃的金额，于是请来了本地著名的侦探协助侦破案件。聪明的侦探根据上述条件巧妙的计算出了盗窃的金额。编程解决侦探是如何知道的？

其实从宏观上划分，小偷的盗窃方案无外乎分为以下两种：

1.  小偷一定会盗窃6号房屋，如果这样小偷就不会盗窃5号了，此时小偷只能从1-4号的某几个房屋中盗窃
2.  小偷一定不会盗窃6号房屋，如果这样，小偷可以从1-5号的某几个房屋中进行盗窃。

其实这样也就出来了，明显递归，这样一来，问题就会转化为如何计算方案1和方案2 两种方案可以盗窃的最大金额这两个小问题。

计算时，我们可以用一个数组house\[\] 保存每个房屋中的现金数量，为了使得数组下标和房屋编号一一对应，我们可以规定数组的第0个位置house\[0\] 等于0，表示不存在0号房屋。

对于栗子来说，house\[\] = \{0,1300,200,500,900,700,400\}，house\[1\] = 1300表示1号房屋中保存了1300现金。

设函数F(n) 表示小偷从前n 个房屋中可以盗窃的最大金额，比如F(3) 代表从1-3 号房屋中可以盗窃的最大金额。

由递归特性：

F( n ) =

*  当n = 0时，F(n) = house\[0\] = 0
 *  当n = 1时，F(n) = house\[1\]
 *  当n >= 2时，F(n) = max(F(n - 2) + house\[n\] , F(n - 1))

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: CleverDetective
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 13:49
     */
    
    public class CleverDetective {
        
    
        public static int StealMoney(int[] house, int n) {
        
            if (n == 0) {
        
                return house[0];
            } else if (n == 1) {
        
                return house[1];
            } else if (n >= 2) {
        
                return Math.max(StealMoney(house, n - 2) + house[n], StealMoney(house, n - 1));
            }
    
            return 0;
        }
    
        public static void main(String[] args) {
        
    
            int[] house = {
        0, 1300, 200, 500, 900, 700, 400};
            System.out.println(StealMoney(house, 6));
    
        }
    
    }

运行结果

![在这里插入图片描述][0cf4d7d2a8474e0793d2edcec2b309f3.png_pic_center]

递归还是老毛病，大量冗余计算。例如在计算StealMoney(house, 4) 时，会先计算 StealMoney(house, 3) 和 StealMoney(house, 2)，但是与StealMoney(house, 4) 同一层的调用中还会计算StealMoney(house , 3) + house\[5\]，这样 StealMoney(house, 3) 就被计算了两次，必然会影响整体的计算效率。

所以动态规划来了，首先构造表：

在初始状态时，可以填写出F(1)的值，

根据递归函数F(n) 和 F(1) 的值，计算F(2)，

F(2) = max(F(0) + house\[2\] , F(1)) = 1300

同样的办法将表格填完。

*  F(3) = max(F(1) + house\[3\] , F(2)) = 1800
 *  F(4) = max(F(2) + house\[4\] , F(3)) = 2200
 *  F(5) = max(F(3) + house\[5\] , F(4)) = 2500
 *  F(6) = max(F(4) + house\[6\] , F(5)) = 2600

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: CleverDetectiveV2
     * @Author: Ding Jiaxiong
     * @Data:2023/3/18 14:05
     */
    
    public class CleverDetectiveV2 {
        
    
        public static int StealMoney(int[] house) {
        
    
            int n = house.length - 1;
            int result[] = new int[house.length];
    
            result[0] = 0;
            result[1] = house[1];
    
            for (int i = 2; i <= n; i++) {
        
                result[i] = Math.max(result[i - 1], result[i - 2] + house[i]);
            }
    
            return result[n];
        }
    
        public static void main(String[] args) {
        
    
            int[] house = {
        0, 1300, 200, 500, 900, 700, 400};
            System.out.println(StealMoney(house));
    
        }
    
    }

运行结果

![在这里插入图片描述][f8f0b084f223440f89623ebf65ca7427.png_pic_center]

没问题。

[0b4551292e964de18ba2b14bac7f213d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/22fd912c972749f1af1f2f563dbb133c.png
[1f5e083448ff45b681a4afdcdc08b05d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0327554817ba4f03a8599502973dc2c8.png
[d210bc29891b4ae39abb215e4dd2c42f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f73aaaf8b0cb493385cdf6d2281f00ea.png
[351e17f7544e44a2967853743546cb0d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e36ed9cac8c24706b10cd56c6706a317.png
[6f0662e36f5744b189e8bbe7e4d4f2f3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/78c487b9679443ae94f0b448a5d4d65b.png
[566d67070129458fb1bfb01476492464.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2522f50fc603483c9b6122457d455e94.png
[ddc9162b1d7048d39cf011e4c2a26b5b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4232dc58aeff4a06a44936f1cc2493cf.png
[87232ee0295c439ea0f293bd0c9b3471.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9f300541ebe44c97800b4da40391c3a9.png
[27b655e162b64b198d35a1286e09d245.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b5497714be1e44899d055714b8fbfe3e.png
[8b361de1efff4e32a1349c8dc3cf5247.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4e2ba2ea0e234866a615248d8f5df14b.png
[cd1d87998b7b423ba042ef7ae186ba2e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5857541e4be148b78d614d62b186d66d.png
[f38c045b383543f78e150e376f40afe9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8fbbcd96542c4e5b84d85168615d3d91.png
[d3c1a17997504deb9db5b148bf6ff6a0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ec798b96f0f845718123f309d1e98035.png
[119b7abe6bd24489a4dd690700b1faac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/528814790df1414d8f94d561e14f4e6c.png
[798ee1148bb948ccaa43f88c15a02f34.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/01cfa17ff4a24961bbebabe535553d82.png
[c2091ffc3226401187f718621448a6fa.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b80c7ce8e1a44ac18677b90db0b0fdfc.png
[535df1bd02214c77b8c125962c49fa06.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a6f8d040e4b64f8eaaeb63956fcb35bf.png
[7993f030547144e6a2ff3779b2d6376e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b46ea65df19b421abd7f95cb4af7572d.png
[980ca5f43e9e421b9f3ef2210b511231.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7665930f95d54453bc19c76078e97bd8.png
[0cf4d7d2a8474e0793d2edcec2b309f3.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/349ed986904d4727b6aad5baf6dd05de.png
[f8f0b084f223440f89623ebf65ca7427.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2cc0b2ee56be438ab42658c7e155cff1.png