dp学习

爱被打了一巴掌 2022-08-21 00:11 113阅读 0赞

给定一个m行n列的矩阵，矩阵每个元素是一个正整数，你现在在左上角（第一行第一列），你需要走到右下角（第m行，第n列），每次只能朝右或者下走到相邻的位置，不能走出矩阵。走过的数的总和作为你的得分，求最大的得分。

输入

第1行：N，N为矩阵的大小。(2 <= N <= 500)  
第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N\[i\] <= 10000)

输出

输出能够获得的最大价值。

输入示例

3  
1 3 3  
2 1 3  
2 2 1

输出示例

dynamic programming中的programming不是指编程而是指表格法。与分治法用于解决含有互不相交的子问题的不同，动态规划用于子问题重叠的问题。（分治法会反复求解公共子问题，而动态规划对每个子问题只求解一次，并**将其保存到一个表格中**）

> 动态规划通常用来解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值的解（max or min)。注意：我们称这样的解为问题的**一个最优解**，而非最优解，因为可能有多个解都达到最优值。——《算法导论》

最优子结构性质：问题的最优解由相关子问题（规模变小了）的最优解组合而成，而这些子问题可以独立求解。

对于这道题利用最优子结构性质求解：设在从起点s到终点e的路径中，经过了点t(x,y)，记f(x,y)为取到的最大价值，此过程中s到t也是最优路径，且t点的上一个点，要么是(x-1,y)要么是(x,y-1)。  
据此可以得到状态转换方程，用于求解该问题：  
f(x,y)：  
\-1，x=0||y=0（因为这是一个达不到的状态）  
value\[1\]\[1\] , x=1&&y=1(起点）  
Max(f(x-1,y),f(x,y-1)) + values\[x\]\[y\]  
[教程][Link 1]

import java.util.Scanner;
    
    public class Main {
    
        static int n;
        static int[][] values = new int[550][550];
        static int[][] dp = new int[550][550];
    
        public static void show(){
            System.out.println("Output:");
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++) System.out.print(values[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()){
                n = in.nextInt();
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++) values[i][j] = in.nextInt();
                }
                //show();
                //initDp();
                int ans = 0;
                for(int x=1;x<=n;x++){
                    for(int y=1;y<=n;y++){
                        if(x==0||y==0) dp[x][y] = -1;
                        else if(x==1&&y==1) dp[x][y] = values[x][y];
                        else dp[x][y] = Math.max(dp[x-1][y], dp[x][y-1]) + values[x][y];
                        if(ans<dp[x][y]) ans = dp[x][y];
                    }
                }
                System.out.println(ans);
            }
        }
    
    }

[Link 1]: http://www.51nod.com/tutorial/course.html#!courseId=1&isCurrent=1