【算法总结】Java实现之动态规划的一般性方法总结

大家好！我是未来村村长，就是那个“请你跟我这样做，我就跟你这样做！”的村长👨‍🌾！

||Algorithm methods||👩‍🌾

​ 未来村村长正推出一系列【Algorithm methods】文章，该系列文章重在总结算法的一般方法，提高个人的逻辑思维能力和解题能力，建立算法解题的知识库。

​ ”算法之路，任重而道远。“🌱|动态规划|🌾

一、动态规划🦽 1、思想

​ 动态规划基本思想：将待求解问题分解成若干个相互连续的子问题，然后从子问题的解得到原问题的解。

2、方法

​ 解决动态规划问题，可以分为五个步骤，分别是确定状态、分解子问题、列转移方程、确定初始条件和边界、确定计算顺序。

（1）确定状态

​ 确定状态即将待求解的问题的每一个过程的状态用一般的数学表达式进行表达，在代码程序中我们使用一个一维数组f[i]，或二维数组f[i][j]进行表示。确定状态和确定子问题，我们都可以通过分解最后一步执行。

（2）分解子问题

​ 要将原问题分解为若干个相互联系的子问题，我们一般从执行的最后一步来进行子问题的分解，逐步分解到问题的初始状态。

（3）列转移方程

​ 子问题从最后一步分解到初始状态，这个分解的一般规律我们称为转移方程，列出该方程即可。

（4）确定初始状态和边界

​ 初始状态指的是原问题的第一步还未执行转移方程的状态，该状态不是推导而来的，而是给定的，这是执行状态转移方程的起点。

​ 这里的边界指的是程序运行的边界，在执行过程中我们需要限定边界，防止程序报错。

（5）确定计算顺序

​ 计算顺序一般都是从初始状态开始，一步一步执行到最终状态。这里的顺序决定了for循环的写法。

3、总结

​ 综上我们总结了动态规划的思想和一般性方法，其实算法问题的本质就是数学问题的代码实现，所以拿到算法题之前，我们要判断该题是什么类型的题，一般使用动态规划解决的问题有三类：最优性问题（求最值）、计数型问题、可行性问题。当然许多动态规划问题可以使用贪心算法来解决，这两种方法也是除了一般的数据结构类型的算法以外最常考的问题。

​ 在动态规划问题中，我们会建立数组f来表示其状态，然后通过表达式类似f[]=f[xxx] + xxx的式子作为状态转移方程，最后通过for循环【代表计算顺序】进行求解得出答案，可见动态规划问题就是一个迭代问题。我们将在以下例题中贯彻该方法。

二、例1：付钱💴 1、题目 （1）描述

​ 你有三种硬币，分别面值2元、5元、7元，硬币足够多，买一本书需要m元，问若使用最少的硬币付清且不需要找零，最少为多少枚。

（2）示例

​ 若m=27，则最少需要5枚[7+5+5+5+5]

2、解题过程 （1）确定状态

​ 确定状态和确定子问题都可以通过分析最后一步的执行过程来完成。

​ 最后一步：我们设最后一枚硬币为k（k∈{2,5,7}），则最后一步的表达式为m-k，这里需要确定的是m-k的硬币组合一定是枚数最少的硬币组合，所以最后一步就是要确定m-k到m的选择那一枚能使枚数最少。

​ 状态设定：我们将 f[m] 设为达到m金额所需要的最少枚数的硬币

（2）分解子问题

​ 继续看最后一步，我们可以将最后一步的状态设定为以下形式：

​ 最后一步的状态：f[m] = min{f[m-2]+1,f[m-5]+1,f[m-7]+1}

（3）列转移方程

​ 我们来看m-k步的子问题：f[m-k] = min{f[m-k-2]+1,f[m-k-5]+1,f[m-k-7]+1}

​ 可见状态转移方程就是：f[m] = min{f[m-2]+1,f[m-5]+1,f[m-7]+1}

（4）确定初始状态和边界

​ 初始状态就是：f[0]=0，因为0元不需要任何硬币。

​ 当m<7时，就会出现越界问题，加入m=3数组不能取f[3-7]，这时我们要给定边界限制。

（5）确定计算顺序

​ 计算顺序一般都是从前往后，若是二维可能是从上到下，从左到右。这里我们以m=13为例，展示计算步骤。

​ 如上图，我们从f[0]开始计算，计算到f[13]时，f[12]之前的需要最少硬币的数量，我们已经求出来了，这时我们只需要比较f[13] = min{f[11]+1,f[8]+1,f[6]+1}，哪一个比较小，即f[13]=min{3+1,4+1,3+1}，得出结果为4。对于越界（即不能不找零钱）的m我们将其状态赋值为-1即可。

3、代码实现

这里的A代表硬币的数量类型【即可以不是2，5，7】，M代表设定的需要金额。

public class Solution{
    public int coinChange(int[] A,int M){
        //确定状态
        int[] f = new int[M+1];
        int n = A.length;
        //初始状态
        f[0]=0;
        //计算顺序
        for(int i=1;i<=M;i++){
            f[i]=Integer.MAX_VALUE;//设定初始状态的无穷大
            //状态转移方程[子问题解决过程]
            for(int j=0;j<n;j++){
                //边界
                if(i>=A[j] && f[i-A[j]] != Integer.MAX_VALUE){//确保子问题有解
                    f[i] = Math.min(f[i-A[j]]+1,f[i]);
                }
            }
        }
        if(f[M]==Integer.MAX_VALUE) f[M] = -1;//如果f[M]不存在答案，设定为-1
        return f[M];
    }
}

二、例2：🤖走格子 1、题目 （1）题目

​ 给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步只能向下走或向右走一步，请问右多少种不同的方式走到右下角。

（2）示例

2、解题过程 （1）确定状态

​ 我们继续分解最后一步，设右下角坐标为（m-1,n-1），那我们最后一步执行之前所处的位置应该是（m-2，n-1）或者（m-1，n-2）。

​ 状态设定：f[i][j]，我们将f[i][j]设定为机器人从（0,0）走到所处位置的所有方式总和。

（2）分解子问题

​ 我们从最后一步来看，设机器人有X种方式从左上角走到（m-2,n-1）,有Y种方式从左上角走到（m-1,n-2），则机器人有X+Y种方式走到（m-1,n-1）。那我们只需要计算到达（m-2,n-1）和（m-1,n-2）的方式数量即可。

（3）列转移方程

​ 根据子问题的分解，我们可以得到状态转移方程，就是每次只需要求到达(x,y)之前的（x-1,y-2）和（x-2,y-1）的方式和。

​ 状态转移方程为：f[i][j] = f[i-1][j] + f[i][j-1]。

（4）确定初始状态和边界

​ 初始状态为：f[0][0] = 1，从（0,0）到（0,0）只有一种方式。

（5）确定计算顺序

​ 计算从f[0][0]开始，f[i][j]种的i和j依次增加1。

3、代码实现

public class Solution{
    public int uniquePaths(int m,int n){
        //确定状态
        int[][] f = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 || j==0){
                    f[i][j] = 1;
                }
                else{
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }
        return f[m-1][n-1];
    }
}

三、例3：🐸跳石头 1、题目 （1）题目

​ 有n块石头分别在x轴的0，1，…，n-1位置，一只青蛙在石头0，向跳到石头n-1，如果青蛙在第i块石头上，它最多可以向右跳距离d[i]，问青蛙能否跳到石头n-1。

（2）示例

​ 输入：d=[2,3,1,1,4]

​ 输出：True；

​ 输入：d=[3,2,1,0,4]

​ 输出：False。

2、解题过程 （1）确定状态

​ 我们来看最后一步，即青蛙能否从n-1跳到n。然后看能否从n-2跳到n-1块石头。由此我们的状态就为能否跳到当前石头。

​ 状态确定：f[j]，表示青蛙能否跳到第j块石头。

（2）分解子问题

​ 刚才我们已经从n-1到n，从n-2到n-1，递推直到0。则可以得出子问题就是，一步步逆推能否跳到第j块石头。

（3）列转移方程

​ 则状态转移方程为：f[j] = OR(f[i] and i+d[i]>=j)；

​ f[i]：青蛙能不能跳到i；

​ i+d[i]>=j：青蛙能否从i跳到j。

（4）确定初始状态和边界

​ 初始状态：f[0]=True，即青蛙可以跳到第0块石头。

（5）确定计算顺序

​ 从第0块，开始判断是否可以跳到第1块，然后依次判断能否跳到第n块。

3、代码实现

public class Soution{
    public boolean canJump(int[] d){
        int n = d.length;
        //状态确定
        boolean f[] = new boolean[n];
        //初始状态
        f[0] = true;
        //计算顺序
        for(int j=1;j<n;j++){
            f[j] = false;
            for(int i=0;i<j;i++){
                if(f[i] && i+d[i]>=j){
                    f[j] = ture;
                    break;
                }
            }
        }
        return f[n-1];
    }
}

四、小结

​ 经过三个例子的代码实现，我们可以进一步总结一个代码实现模板，即一般顺序为状态确定、初始化状态、计算顺序、边界限定、状态转移方程。

public class Soution{
    public boolean xxx(){
        //状态确定
        int f[] = new int[x];
        //初始化状态
        f[0] = xx;
        //计算顺序
        for(int i=1;i<xx;i++){
            //边界限定
            if(xxx){
            	//状态转移方程
            	f[i] = f[xx] + xxx
            }
        }
        return f[n-1];
    }
}

——————————————————————

作者：未来村村长

参考：B站-九章算法-动态规划视频

个人网站：www.76pl.com

👨‍🌾还有人不关注我的话，我真的会谢👩‍🌾

——————————————————————