深入理解动态规划

ゝ一纸荒年。 2022-03-16 01:30 212阅读 0赞

**动态规划的核心:记住已经解决过的子问题的解**

A * "1+1+1+1+1+1+1+1 =？" *
    
    A : "上面等式的值是多少"
    B : "8!"
    
    A *在上面等式的左边写上 "1+" *
    A : "此时等式的值为多少"
    B : "9!"
    A : "怎么这么快知道答案？"
    A : "在8的基础上加1就行了"
    A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

**例题:**

描述:
    
        7 
       3 8 
      8 1 0 
     2 7 4 4 
    4 5 2 6 5 
    
    上面显示了一个数字三角形。编写一个程序，计算从顶部开始到底部某处的路径上传递的最大数字总和。每个步骤可以沿对角线向下滑动，也可以沿斜向下滑动到右侧。 
    输入
    
    您的程序是从标准输入读取。第一行包含一个整数N：三角形中的行数。以下N行描述了三角形的数据。三角形中的行数> 1但<= 100.三角形中的数字全部为整数，介于0到99之间。
    产量
    
    你的程序是写入标准输出。最高总和写为整数。
    样本输入
    
    5
    7
    3 8
    8 1 0 
    2 7 4 4
    4 5 2 6 5
    输出:
    
    30

**递归解法:**

import java.util.Scanner;
    
    public class Main {
    	public static final int size = 100;
    	public static int a[][] = new int[size + 1][size + 1];
    	public static int n;
    
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		n = s.nextInt();
    		for (int i = 1; i <= n; i++) {
    			for (int j = 1; j <= i; j++) {
    				a[i][j] = s.nextInt();
    			}
    		}
    		System.out.println(MaxSum(1, 1));
    	}
    
    	private static int MaxSum(int i, int j) {
    		// TODO 自动生成的方法存根
    		if(i==n) {
    			return a[i][j];
    		}else {
    			int x=MaxSum(i+1,j);
    			int y=MaxSum(i+1,j+1);
    			return Math.max(x, y)+a[i][j];
    		}
    	}
    }

**这段代码提交到POJ，显示运行超时，为什么呢？因为我们重复了大量的运算。**

**改进：每次计算好MaxSum(i,j)后，就把它保存起来，下次要用的时候直接拿出来用，不用再执行重复的运算。**

package test;
    
    import java.util.Scanner;
    
    public class Main {
    	public static final int size = 100;
    	public static int a[][] = new int[size + 1][size + 1];
    	public static int maxSum[][] = new int[size + 1][size + 1];
    	public static int n;
    
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		n = s.nextInt();
    		for (int i = 1; i <= n; i++) {
    			for (int j = 1; j <= i; j++) {
    				a[i][j] = s.nextInt();
    				maxSum[i][j]=-1;
    			}
    		}
    		System.out.println(MaxSum(1, 1));
    	}
    
    	private static int MaxSum(int i, int j) {
    		// TODO 自动生成的方法存根
    		if(maxSum[i][j]!=-1) {
    			return maxSum[i][j];
    		}
    		if(i==n) {
    			return a[i][j];
    		}else {
    			int x=MaxSum(i+1,j);
    			int y=MaxSum(i+1,j+1);
    			maxSum[i][j]=Math.max(x, y)+a[i][j];
    			return maxSum[i][j];
    		}
    	}
    }

**这次提交到POJ就Accept了**

**虽然Accept了，但是使用递归需要用到大量的堆栈，容易造成栈溢出，我们应该把递归改为动态规划。**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUEhZVA_size_16_color_FFFFFF_t_70][]**

**右边的表怎么得到？**

**最后一行是 4 5 2 6 5 ，倒数第二行:2可以与4或5相加，明显5更大，5+2即为7,7可以和5或2相加，明显与5相加更大，5+7=12**

**以此类推。**

**倒数第三行:8可以与7或12相加，明显与12相加更大，即为20，以此类推。**

**动态规划解法:**

import java.util.Scanner;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		int n = s.nextInt();
    		int a[][] = new int[n + 1][n + 1];
    		for (int i = 1; i <= n; i++) {
    			for (int j = 1; j <= i; j++) {
    				a[i][j] = s.nextInt();
    			}
    		}
    
    		for(int i=n-1;i>0;i--) {
    			for(int j=1;j<=i;j++) {
    				a[i][j]=Math.max(a[i+1][j], a[i+1][j+1])+a[i][j];
    			}
    		}
    		System.out.println(a[1][1]);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0haUEhZVA_size_16_color_FFFFFF_t_70]: /images/20220316/ddd629bd6532427f809e8b258feb80be.png