题1：

877. 石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

 

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

输入：piles = [3,7,2,3]
输出：true

 

提示：

• 2 <= piles.length <= 500
• piles.length 是 偶数
• 1 <= piles[i] <= 500
• sum(piles[i]) 是 奇数

 1 class Solution {
 2     public boolean stoneGame(int[] piles) {
 3         int n=piles.length;
 4         Result[][] dp=new Result[n][n];
 5         //区间dp
 6         //dp[i][j]表示i~j石堆的结果，fir是先手最大，sec是后手最大
 7         for (int i=0;i<n;i++){
 8             for (int j=i;j<n;j++){
 9                 dp[i][j]=new Result(0,0);
10             }
11         }
12         //边界条件
13         for (int i=0;i<n;i++) {
14             dp[i][i].fir=piles[i];
15             dp[i][i].sec=0;
16         }
17         // 斜着 倒着遍历
18         for (int i=n-2;i>=0;i--) {
19             for (int j=i+1;j<n;j++) {
20                 // 先手选择左边和右边的结果
21                 int left=dp[i+1][j].sec+piles[i];
22                 int right=dp[i][j-1].sec+piles[j];
23                 if (left>right) {
24                     dp[i][j].fir=left;
25                     dp[i][j].sec=dp[i+1][j].fir;
26                 }else {
27                     dp[i][j].fir=right;
28                     dp[i][j].sec=dp[i][j-1].fir;
29                 }
30             }
31         }
32         return dp[0][n-1].fir>dp[0][n-1].sec;
33     }
34 }
35 
36 class Result{
37     int fir;
38     int sec;
39     //fir表示先手
40     //sec表示后手
41     Result(int fir,int sec){
42         this.fir=fir;
43         this.sec=sec;
44     }
45 }

思路：通用动态规划思路如注释。

题2：

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

 1 class Solution {
 2     public int minPathSum(int[][] grid) {
 3         int m=grid.length,n=grid[0].length;
 4         int[][] dp=new int[m+1][n+1];
 5         for (int i=0;i<=m;i++) Arrays.fill(dp[i],Integer.MAX_VALUE);
 6         dp[0][1]=0;
 7         dp[1][0]=0;
 8         for (int i=1;i<=m;i++) {
 9             for (int j=1;j<=n;j++) {
10                 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
11             }
12         }
13         return dp[m][n];
14     }
15 }

思路：dp[i][j]表示到达i-1,j-1坐标的最小值。为了防止数组越界，多开一行一列数组。边界条件，要让dp[1][1] 为grid[0][0]， 让dp[1][0]或者dp[0][1]一个取0，其余初始值取最大值。