第一题 礼物的最大价值
在一个 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);
}
}
第二题 最长不含重复字符的子字符串
