Java日记2018-05-16

第一题 礼物的最大价值

在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。给定一个棋盘，求拿到礼物的最大价值。

解题思路是动态规划来计算。分开来想，由于只能向上或向下移动一格。那么对于dp[i]代表每一列的最大礼物值。对于m行n列的礼物，每向右边一格代表的还是dp[i-1]+value(当前值)，或向下一格实际代表dp[i]+value(当前值)。因为向右dp实际列变大，向下实际还是那同一列的dp。（初始化dp[0]，因为i每向下走一格，对于初始列的最大礼物值就要加当前行0列的值）

public class GetMost {
    public static void getmost(int[][] arr) {
        if(arr==null) return;
        int m=arr.length;
        int n=arr[0].length;
        int[] dp = new int[n];
        for(int i=0;i<m;i++) {
            //初始化dp[0]，因为i每向下走一格，对于初始列的最大礼物值就要加当前行0列的值
            dp[0]+=arr[i][0];
            for(int j=1;j<n;j++) {
                dp[j]=Math.max(dp[j], dp[j-1])+arr[i][j];
            }
        }
        
        System.out.println("the result:"+dp[n-1]);
    }
    public static void main(String[] args) {
        int[][] arr = {{1,10,3,8},{12,2,9,6},{5,7,4,11},{3,7,16,5}};
        getmost(arr);
    }

}

第二题 最长不含重复字符的子字符串