Table of Contents

一、动态规划解决游戏问题

这部分题目练习空间优化技巧，对于每一题直接编写空间优化后的代码。

64. 最小路径和

注重边界的问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n+1];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 0) {
                    dp[j] = dp[j-1] + grid[i][j-1];
                    continue;
                }
                if (j == 1) {
                    dp[j] = dp[j] + grid[i][j-1];
                    continue;
                }
                dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j-1];
            }
        }
        return dp[n];
    }
}