动态规划例题总结

<font size="6px">
一、01背包问题</font>
题目描述：有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
       1<=n<=100
       1<=wi,vi<=100
       1<=w<=10000
样例：
输入
       n=4
       (w,v)={(2,3),(1,2),(3,4),(2,2)}
       W=5
输出
       7(选择0，1，3号物品)
因为对每个物品只有选和不选两种情况，所以称这个问题为01背包

<font color="red" size="5px">解法一:</font>
思路分析：这一种解法采用的是深度优先搜索，遍历每一种情况，选取其中的最大值。深搜的情况分为两种，一种是选当前位置，一种是不选当前位置。解法首先调用自定义的函数，然后分为两种情况，如果是不选的话，最大重量W不变，可选位置current+1。如果选的话，最大重量变为W - w[current]，可选位置current+1。继续递归。然后每次递归过程中，都要选取两种情况中最大的。最后要确定出口，输出结果。

    static int W=5;                                             //最大重量
    static int n=4;                                             //物品数
    static int[] w= {2,1,3,2};                                  //每个物体的重量
    static int[] v= {3,2,4,2};                                  //每个物体的价值
    
    public static void main(String[] args) {
        int x=f(W,0);                                           //调用自定义函数
        System.out.println(x);                                  //输出结果
    }
    private static int f(int W, int current) {
        if (W <= 0) {                                                   //出口判断
            return 0;
        }
        if (current == n) {                                             //出口判断
            return 0;
        }
        int value1 = f(W, current + 1);                                //不选的情况
        if (W >= w[current]) {
            int value2 = v[current] + f(W - w[current], current + 1);   //选当前的情况
            int temp = Math.max(value1, value2);                        //取两者较大值
            return temp;
        }
        return value1;
    }

<font color="red" size="5px">解法二:</font>
思路分析：其实第二种解法只是第一种解法的简单优化，所以只标注一些优化后的注释。优化在于每次递归其实都会有重复的地方，故创建一个记忆数组，用于记录之前递归中的值。记忆数组是一个二维数组，arr【当前位置current】【剩余最大乘重量】。记忆数组要先初始化，将所有位置置为-1。在方法调用中，如果值大于0，则表明之前已经调用过，可以直接获取值并返回。

    static int W=5;                                             //最大重量
    static int n=4;                                             //物品数
    static int[] w= {2,1,3,2};                                  //每个物体的重量
    static int[] v= {3,2,4,2};                                  //每个物体的价值
    static int[][] arr=new int[n][W+1];                         //记忆数组                  
    
    public static void main(String[] args) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < W + 1; j++) {
                arr[i][j] = -1;                                 //初始化记忆数组
            }
        }
        int x = f(W, 0);                                        // 调用自定义函数
        System.out.println(x);                                  // 输出结果
    }
    //记忆型递归
    private static int f(int W, int current) {
        if (W <= 0) {
            return 0;
        }
        if (current == n) {
            return 0;
        }
        if (arr[current][W] >= 0) {                                     //如果记忆数组中含有值
            return arr[current][W];                                     //取值，直接返回
        }
        int value1 = f(W, current + 1);
        int value2 = 0;
        if (W >= w[current]) {
            value2 = v[current] + f(W - w[current], current + 1);
        }
        int judge = Math.max(value1, value2);                           //选取两种情况中的较大值
        arr[current][W] = judge;                                        //存入记忆数组中
        return judge;
    }

<font color="red" size="5px">解法三:</font>
思路分析：这题采用的是dp解法，博主可能无法完全用语言描述清楚dp解法，故需先自己了解原理。这个题采用了dp解法，需要使用到Excel表格，第一行代表最大载重量，第一列代表每一种物品。需要首先初始化表格中的第二行，也就是f方法中的第一个for循环。然后遍历每一行，也是有两种情况，第一种情况是不取，那就直接选取上一行的较大值。第二种情况是取，然后就用i号物品的价值+上一行中对应的最大载重量。其实就是填表格，直到填完最后一个格子，最后一个格子即为最大值。（博主已经尽力描述了，如果没有让你明白，深感抱歉。）

在这里插入图片描述

static int W=5;                                             //最大重量
    static int n=4;                                             //物品数
    static int[] w= {2,1,3,2};                                  //每个物体的重量
    static int[] v= {3,2,4,2};                                  //每个物体的价值
    static int[][] arr=new int[n][W+1];                         //记忆数组                  
    
    public static void main(String[] args) {
        int x = f(W, 0);                                        // 调用自定义函数
        System.out.println(x);                                  // 输出结果
}
    //dp解法
    private static int f(int W, int current) {
        for (int i = 0; i < W + 1; i++) {
            if (i >= w[0]) {
                arr[0][i] = v[0];                               //初始化第一行
            }   
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < W + 1; j++) {
                if (j >= w[i]) {
                    arr[i][j] = Math.max(v[i] + arr[i - 1][j - w[i]], arr[i - 1][j]);   //选取两种情况中的较大值
                } else {
                    arr[i][j] = arr[i - 1][j];                      //只有一种情况，直接存入
                }
            }
        }
        return arr[n - 1][W];
    }

<font size="6px">
二、数字三角形问题</font>
**题目描述：在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出最大和即可，不比给出路径。三角形的行数大于1小于等于100，数字为0~99
       1<=n<=100
       1<=wi,vi<=100
       1<=w<=10000
样例：
输入

在这里插入图片描述
输出
30

<font color="red" size="5px">解法一:</font>
思路分析：这题也是采用深搜解法。。首先调用自定义的函数f1，首先获取三角形的最大行数maxLength。如果maxLength==行数i，则直接返回triangle[i][j]。否则继续递归调用，用（i,j）上的值加上下一行的最大值，并返回。最后输出结果

public static void main(String[] args) {
        int[][] triangle= {
                {7},
                {3,8},
                {8,1,0},
                {2,7,4,4},
                {4,5,2,6,5}
        };
        int temp=f2(triangle,0,0);                              //调用自定义函数
        System.out.println(temp);
    }
    //dfs解法
    public static int f1(int[][] triangle,int i,int j) {
        int maxLength=triangle.length;                          //三角形的行数
        if(i==maxLength-1) {
            return triangle[i][j];                              //到达最后一行，直接返回
        }else {
            return triangle[i][j]+Math.max(f1(triangle,i+1,j), f1(triangle,i+1,j+1));   //（i，j）位上的数字加上下一行的较大值
        }
    }

<font color="red" size="5px">解法二:</font>
思路分析：这题采用的是dp解法。首先还是相当于建表格。首先初始化三角形的最后一行，将他存入新的二维数组中。然后从倒数第二行开始往上填，每次都选取下一个中的较大值。直到填完第一行。二维数组中的[0][0]号位即为结果。

在这里插入图片描述

public static void main(String[] args) {
        int[][] triangle= {
                {7},
                {3,8},
                {8,1,0},
                {2,7,4,4},
                {4,5,2,6,5}
        };
        int temp=f2(triangle);                              //调用自定义函数
        System.out.println(temp);
    }
    //dp解法
        public static int f2(int[][] triangle) {
            int maxLenth=triangle.length;                       //获取最大行数
            int[][] arr=new int[maxLenth][maxLenth];            //新建一个二维数组
            for(int q=arr.length-1;q>=0;q--) {
                arr[maxLenth-1][q]=triangle[maxLenth-1][q];     //初始化二维数组的最后一行
            }
            for(int k=arr.length-2;k>=0;k--) {
                for(int c=0;c<=k;c++) {
                    arr[k][c]=triangle[k][c]+Math.max(arr[k+1][c], arr[k+1][c+1]);  //从下往上填，选择下一行中较大的数字+(k,c)号位上的值
                }
            }
            return arr[0][0];                                   //返回结果
        }

<font size="6px">
三、完全背包问题</font>
**题目描述：有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
样例：
      1<=n<=100
      1<=wi,vi<=100
      1<=W<=10000
输入
n=5
(w,v)={(2,3),(1,2),(3,4),(2,2)}
输出
10

<font color="red" size="5px">解法一:</font>
思路分析：这题读者可以将他与01背包类比。这道题的和第一题的不同之处在于没有限定一个物品有多少个，因此可以选多个同一种物品。分析之后，和第一题一样，存在两种情况。第一种情况是不取，那就直接取arr[i-1][j]中的值。第二种情况是取，那么就是v[i]+arr[i][j-w[i]]。也是和前面的题一样，填表格。可以先将第一行和第一列初始化，然后逐个空填满表格，最后一个空即为最大值。

在这里插入图片描述

public static void main(String[] args) {
        int answer=f();
        System.out.println(answer);
    }
    static int W=2;                                             //最大重量
    static int n=4;                                             //物品数
    static int[] w= {2,1,3,2};                                  //每个物体的重量
    static int[] v= {3,2,4,2};                                  //每个物体的价值
    public static int f() {
        int[][] arr=new int[n][W+1];
        for(int i=0;i<W+1;i++) {
            arr[0][i]=i/w[0]*v[0];                              //初始化第一行
        }
        for(int i=0;i<n;i++) {
            arr[i][0]=0;                                        //初始化第一列
        }
        for(int i=1;i<n;i++) {      
            for(int j=1;j<W+1;j++) {
                if(j>=w[i]) {                                   //如果该物品重量小于最大载重量
                int temp1=arr[i-1][j];                          //第一种情况，不取该物品                       
                int temp2=v[i]+arr[i][j-w[i]];                  //第二种情况，不取该物品
                arr[i][j]=Math.max(temp1, temp2);
                }else {                                         //否则
                    arr[i][j]=arr[i-1][j];                      //直接是不取该物品
                }
            }
        }
        return arr[n-1][W];
    }

<font size="6px">
四、最长上升子序列的问题</font>
**题目描述：最长递增子序列的长度
输入
4 2 3 1 5 6
输出
3（因为2 3 5组成了最长递增子序列）

<font color="red" size="5px">解法一:</font>
思路分析：第一种解法采用的简单的暴力解法。在函数中首先初始化最大长度max=0。然后两层循环遍历每一个字符，如果后面的字符比前面的字符打，就长度+1。

public static void main(String[] args) {
        int[] arr = { 4, 2, 3, 1, 5 };
        System.out.println(f(arr));                         // 调用自定义的函数
    }

    private static int f(int[] arr) {
        int max = 0;                                        //记录最大长度
        for (int i = 0; i < arr.length; i++) {
            int p = i;                                      //指针，初始化为i号字符
            int cnt = 1;                                    //初始化长度为1，因为i号位就是第一个字符
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] > arr[p]) {                              
                    cnt++;                                  //长度加一
                    p = j;                                  //p变更为j号位
                }
            }
            if (cnt > max) {
                max = cnt;                                  //变更最大长度
            }
        }
        return max;
    }

<font color="red" size="5px">解法二:</font>
思路分析：第二种解法是dp解法。这里的想法是首先初始化一个长度数字，将每个位置置为1，也就是最开始每个数字都是独立的,所以单个数字的长度为1。然后遍历每一个数字，第二层循环遍历i号位之前的每一个数字，如果i号位上的数字大于j号位上的数字，则说明构成递增序列。因此就把长度数组j号位上的值+1和长度数组上i号位已经有的值比较大小，取较大值。最后遍历长度数组，输出结果。

在这里插入图片描述

//dp解法
    public static void main(String[] args) {
        int[] arr = { 4, 2, 3, 1, 5 };
        f(arr);                         // 调用自定义的函数
    }
    public static void f(int[] arr) {
        int[] list=new int[arr.length];                     //新建一个长度数组
        for(int i=0;i<list.length;i++) {        
            list[i]=1;                                      //首先初始化每个位置为1（就是只有单个独立字符）
        }
        for(int i=0;i<arr.length;i++) {                     //遍历每一个数字
            for(int j=i-1;j>=0;j--) {                       //遍历i号位数字之前的每个数字
                if(arr[i]>arr[j]) {                         //如果i号位的数字大于j号位的数字
                    list[i]=Math.max(list[j]+1, list[i]);   //j号位数字的最大长度+1和i号位上的最大长度比较，取较大值
                }
            }
        }
        int max=0;
        for(int i=0;i<list.length;i++) {
            if(list[i]>max) {
                max=list[i];                                //遍历长度数组，获取最大长度
            }
        }
        System.out.println(max);
        
    }