【数据结构与算法之动态规划】动态规划的基本思想

àì夳堔傛蜴生んèń 2024-03-25 19:16 132阅读 0赞

#### 【数据结构与算法之动态规划】动态规划的基本思想 ####

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

*   *   *  【数据结构与算法之动态规划】动态规划的基本思想

之前我们讲的递归，它的核心思想就是将求解的问题分解成若干个具有相同属性的子问题，通过子问题的解得到原问题的解。

其实递归算法最主要的缺陷就是在递归调用过程中存在了冗余的运算，这会增加算法的时间复杂度和空间复杂度。

而`动态规划算法` 就可以消除这些冗余计算，提升算法性能。

【举个栗子】走楼梯问题。

一个楼梯共有10级台阶，一个人从下往上走，每次可以走1级台阶，也可以走2级台阶。问有多少中方法走完这10级台阶？

随便两种情况：

*  1 → 1 → 1 → 1 → 1 → 1 → 1 → 1 → 1 → 1
 *  2 → 1 → 1 → 1 → 1 → 1 → 1 → 1 → 1

很明显，方式有非常多。

但是想一个问题，如果要走到第10级台阶，则必然存在且仅存在下面两种情况：

1.  先到第8级台阶，走2级，到达第10级
2.  先到第9级台阶，走1级，到达第10级

假设这个人走到第8级台阶走法有x种，走到第9级台阶走法有y 种，那么他要走上第10级台阶的走法就一定是 x + y种。

这样问题仿佛就清晰了，我们用F(10) 表示这个人登上第10级台阶的走法的数量，用F(9) 表示他登上第9级台阶的走法的数量，用F(8) 表示登上第8级台阶的走法的数量，→ 一定有 F(10) = F(9) + F(8)。

类比F(10)，可以得到F(9) = F(8) + F(7)、F(8) = F(7) + F(6)…

当只有1级台阶时，F(1) = 1，只有2级台阶时,F(2) = 2 【要么走两次1步，要么走一次2步】

∴ 可以得到F(n) 的计算公式：

*  当n = 1时，F(n) = 1
 *  当n = 2时，F(n) = 2
 *  当n > 2时，F(n) = F(n - 1) + F(n - 2)

Java 求解描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ClimbStairs
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 20:13
     */
    
    public class ClimbStairs {
        
    
        private static int getClimbWays(int n) {
        
            if (n == 1) {
        
                return 1;
            } else if (n == 2) {
        
                return 2;
            } else {
        
                return getClimbWays(n - 1) + getClimbWays(n - 2);
            }
        }
    
        public static void main(String[] args) {
        
    
            int climbWays = getClimbWays(10);
            System.out.println(climbWays);
    
        }
    
    }

运行结果

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

这就是走10级楼梯的走法数量，一共89 种。纯纯的递归。

其实我们仔细思考就会发现，算法进行过程中进行了很多冗余计算，比如计算F(n) 时要先算F(n - 1)和F(n - 2)，而计算F(n - 1) 时，要先计算F(n - 2) 和 F(n - 3)，这样F(n - 2) 就算了两次。这就造成了冗余计算。

递归算法是由上而下的，例如从F(10) 开始逐层分解该问题，在重复调用自身的同时，问题规模不断缩小。

其实我们还可以自底向上计算，通过F(1) =1 、F(2) = 2 计算出F(3) = 3，再通过F(2) = 2、F(3) = 3计算出 F(4) = 5，以此类推，一直计算出F(n)，这种方式会将每一步的结果都记录下来，没有冗余计算。

这种利用问题本身的递归特性自底向上计算出最优解的方法 → 【动态规划算法】

Java 再次实现走楼梯问题：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ClimbStairs
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 20:13
     */
    
    public class ClimbStairs {
        
    
        private static int getClimbWays(int n) {
        
    
            int a = 1;
            int b = 2;
            int tmp = 0;
            int i = 0;
    
            if (n == 1) {
        
                return 1;
            } else if (n == 2) {
        
                return 2;
            } else {
        
                for (i = 3; i <= n; i++) {
        
                    tmp = a + b;
                    a = b;
                    b = tmp;
                }
    
                return tmp;
            }
    
        }
    
        public static void main(String[] args) {
        
    
            int climbWays = getClimbWays(10);
            System.out.println(climbWays);
    
        }
    
    }

运行结果

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

在使用动态规划算法解决问题时需要把握如下两个基本要素：

1.  具备最优子结构
2.  具备子问题重叠性质。

[ef0e29fbea9b4520892ce5cb85c44b60.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b380eb5d44fb49f0be2598a24b2dcffc.png
[ce94f9a83e084b5ea3bd9541cd315f4c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0d1ecfbb2b3545c58169cff34ca6526a.png