动态规划

刺骨的言语ヽ痛彻心扉 2022-07-29 11:46 111阅读 0赞

1.  首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段
2.  动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”。
3.  最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
4.  动态规划的核心是“状态的表达”和“状态转移方程的建立”，状态的意义的确立直接关系到状态转移方程能否建立正确。
5.  动态规划问题常用的有两种方法：  
    a. “自底向上”的递推。利用“问题的最优解包含子问题的最优解”，由于是“自底向上”求解的，就是说子子问题的最优解已经确立，子问题的最优解就可以从这些子子问题的最优解中确定出来。**递推的关键是边界和计算顺序。**  
    b. 记忆化搜索。它是按照“自顶向下”的顺序求解的。与分治法将问题划分为互不相交的子问题不同的是，动态规划用于子问题重叠的情况（不同的子问题具有公共的子子问题），这样就必须要解决“子问题重复计算”的问题，否则会做大量的重复计算，效率急剧下降（就是单纯的搜索，这也就是为什么搜索只能过动态规划问题的一部分测试点的的原因）。记忆化搜索仍按照搜索的过程求解问题，但在搜索的工程中会保存每个子问题的解（用一个数组或散列表）。当需要一个解时，先去检查是否保存过此解，有，直接返回，否则按通常方式计算，并加以保存。注意，搜索可以剪枝！！！

> 一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。  
> 更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。  
> 记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，

具体问题分析：

1002 数塔取数问题
    基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏  关注
    一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
    每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。
    
       5
      8 4
     3 6 9
    7 2 9 5
    
    例子中的最优方案是：5 + 8 + 6 + 9 = 28
    Input
    第1行：N，N为数塔的高度。(2 <= N <= 500)
    第2 - N + 1行：每行包括1层数塔的数字，第2行1个数，第3行2个数......第k+1行k个数。数与数之间用空格分隔（0 <= A[i] <= 10^5) 。
    Output
    输出最大值
    Input示例
    4
    5
    8 4
    3 6 9
    7 2 9 5
    Output示例
    28

分析：

1.确定状态： 把当前的位置(i,j)看成一个状态，定义状态(i,j)的指标函数d(i,j)为从(i,j)点出发时能得到的最大和（包括(i,j)本身）。在这个状态下，问题解为d(1,1)  
2. 确定状态转移方程：从格子(i,j)出发有两种决策。往左走，走到(i+1,j)之后需要求“从(i+1,j)出发能得到的最大和”这一问题，即d(i+1,j)，同样的，往右走，到达(i+1,j+1)后需要求解d(i+1,j+1)这一问题。即状态转移方程为：d(i,j)=a(i,j) + Max\{d(i+1,j),d(i+1,j+1)\}。数据结构a用于存储输入数据。  
3. 具体实现

//用递推来做，相当于一棵二叉树，先确定最底层，然后依次确定上一层，知道第一层。
    import java.util.Scanner;
    
    public class Main {
    
        public static void show(int n,int[][] nums){
            System.out.println("Output trangels:");
            for(int i=1;i<=n;i++){
                for(int j=1;j<=i;j++) System.out.print(nums[i][j]+" ");
                System.out.println();
            }
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();
                int[][] triangle = new int[n+10][n+10];
                int[][] dp = new int[n+10][n+10];
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=i;j++) triangle[i][j] = in.nextInt();
                }
                //最后一层，作为起始边界。
                for(int j=1;j<=n;j++) dp[n][j] = triangle[n][j];
                //向上递推
                for(int i=n-1;i>=1;i--){
                    for(int j=1;j<=i;j++){
                        dp[i][j] = triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
                    }
                }
                System.out.println(dp[1][1]);
            }
        }
    
    }

//记忆化搜索
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class Main {
    
        public static int n;
        public static int[][] dp , triangle;
        public static void show(int n,int[][] nums){
            System.out.println("Output trangels:");
            for(int i=1;i<=n;i++){
                for(int j=1;j<=i;j++) System.out.print(nums[i][j]+" ");
                System.out.println();
            }
        }
        //利用赋值语句的返回值是所赋的值这一特性，将保存dp[i][j]的工作合并到函数的返回语句中。
        public static int memorySearch(int i,int j){
            if(dp[i][j]!=-1) return dp[i][j];
            if(i==n) return triangle[i][j];//搜索到最后一层了
            else return dp[i][j] = triangle[i][j] + Math.max(memorySearch(i+1, j), memorySearch(i+1, j+1));
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                n = in.nextInt();
                triangle = new int[n+10][n+10];
                dp = new int[n+10][n+10];
                //状态-1,代表没有访问过！！
                for(int i=1;i<=n;i++) Arrays.fill(dp[i], -1);
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=i;j++) triangle[i][j] = in.nextInt();
                }
                int res = memorySearch(1, 1);
                System.out.println(res);
            }
        }
    
    }

note：

1.  分析出问题的最优子结构性质
2.  构造状态
3.  确定状态转移方程
4.  选用合适的方法求解