第一題 禮物的最大價值

在一個 m*n 的棋盤的每一個格都放有一個禮物，每個禮物都有一定價值（大于 0）。從左上角開始拿禮物，每次向右或向下移動一格，直到右下角結(jié)束。給定一個棋盤，求拿到禮物的最大價值。

解題思路是動態(tài)規(guī)劃來計算。分開來想，由于只能向上或向下移動一格。那么對于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);
    }

}

第二題 最長不含重復字符的子字符串