Problem Statement
We have a 2×N grid. We will denote the square at the i-th row and j-th column (1≤i≤2, 1≤j≤N) as (i,j).
You are initially in the top-left square, (1,1). You will travel to the bottom-right square, (2,N), by repeatedly moving right or down.
The square (i,j) contains Ai,j candies. You will collect all the candies you visit during the travel. The top-left and bottom-right squares also contain candies, and you will also collect them.
At most how many candies can you collect when you choose the best way to travel?
Constraints
- 1≤N≤100
- 1≤Ai,j≤100 (1≤i≤2, 1≤j≤N)
Input
Input is given from Standard Input in the following format:
N
A1,1 A1,2 … A1,N
A2,1 A2,2 … A2,N
Output
Print the maximum number of candies that can be collected.
Sample Input 1
5
3 2 2 4 1
1 2 2 2 1
Sample Output 1
14
The number of collected candies will be maximized when you:
- move right three times, then move down once, then move right once.
Sample Input 2
4
1 1 1 1
1 1 1 1
Sample Output 2
5
You will always collect the same number of candies, regardless of how you travel.
Sample Input 3
7
3 3 4 5 4 5 3
5 3 4 4 2 3 2
Sample Output 3
29
Sample Input 4
1
2
3
Sample Output 4
5
分析：从（0,0）到（2，n）求最大数 动态规划
package VJ3;import java.util.Scanner;public class Main{static int a[][] = new int[3][101];static int dp[][] = new int[3][101];static int n;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 1; i <= 2; i++) {for (int j = 1; j <= n; j++) {a[i][j] = sc.nextInt();}}solve();System.out.println(dp[2][n]);}private static void solve() {dp[1][1] = a[1][1];for (int i = 1; i <= 2; ++i) {for (int j = 1; j <= n; ++j) {if (i == 1)dp[i][j] = dp[i][j - 1] + a[i][j];//第一行elsedp[i][j] = Math.max(dp[i - 1][j]+a[i][j], dp[i][j - 1] + a[i][j]);//第二行}}}
}