leetcode 576. Out of Boundary Paths | 576. 出界的路径数（暴力递归-＞傻缓存-＞dp）

偏执的太偏执、 2022-08-28 08:56 150阅读 0赞

## 题目 ##

[https://leetcode.com/problems/out-of-boundary-paths/][https_leetcode.com_problems_out-of-boundary-paths]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

经典的 从递归到 dp，不多说，上代码。

class Solution { 
        public static final int MOD = (int) (Math.pow(10, 9) + 7);
    
        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { 
            // 【Solution 1】暴力递归
    // return process1(m, n, maxMove, startRow, startColumn);
            
            // 【Solution 2】傻缓存
           // int[][][] dp = new int[maxMove + 1][m][n];
           // for (int move = 1; move <= maxMove; move++) { // 剩余步数move=0时，dp表内的位置均不存在paths
           // for (int i = 0; i < m; i++) { 
           // Arrays.fill(dp[move][i], -1);
           // }
           // }
           // return process2(m, n, maxMove, startRow, startColumn, dp);
            
            // 【Solution 3】dp
            int[][][] dp = new int[maxMove + 1][m][n];
            for (int move = 1; move <= maxMove; move++) { 
                for (int i = 0; i < m; i++) { 
                    for (int j = 0; j < n; j++) { 
                        int path = 0;
                        path += (i - 1 < 0) ? 1 : dp[move - 1][i - 1][j]; path %= MOD;
                        path += (i + 1 == m) ? 1 : dp[move - 1][i + 1][j]; path %= MOD;
                        path += (j - 1 < 0) ? 1 : dp[move - 1][i][j - 1]; path %= MOD;
                        path += (j + 1 == n) ? 1 : dp[move - 1][i][j + 1]; path %= MOD;
                        dp[move][i][j] = path;
                    }
                }
            }
            return dp[maxMove][startRow][startColumn];
        }
    
    // public int process1(int m, int n, int remain, int i, int j) { 
    // if (remain < 0) return 0;
    // if (i == m || j == n || i < 0 || j < 0) return 1;
    // return process1(m, n, remain - 1, i + 1, j) +
    // process1(m, n, remain - 1, i - 1, j) +
    // process1(m, n, remain - 1, i, j + 1) +
    // process1(m, n, remain - 1, i, j - 1);
    // }
    
    // public int process2(int m, int n, int remain, int i, int j, int[][][] dp) { 
    // if (remain < 0) return 0;
    // if (i == m || j == n || i < 0 || j < 0) return 1;
    // if (dp[remain][i][j] >= 0) return dp[remain][i][j];
    // dp[remain][i][j] = process2(m, n, remain - 1, i + 1, j, dp) % (MOD);
    // dp[remain][i][j] += process2(m, n, remain - 1, i - 1, j, dp); dp[remain][i][j] %= MOD;
    // dp[remain][i][j] += process2(m, n, remain - 1, i, j + 1, dp); dp[remain][i][j] %= MOD;
    // dp[remain][i][j] += process2(m, n, remain - 1, i, j - 1, dp); dp[remain][i][j] %= MOD;
    // return dp[remain][i][j];
    // }
    }

#### “带缓存的递归” 与 “自底向上的dp” 之争 ####

补充一条：一些题想做斜率优化的话，就只能自底向上dp了  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_out-of-boundary-paths]: https://leetcode.com/problems/out-of-boundary-paths/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d595e8c13870406a80ee2a7190cd3392.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1f4dc56adc8745c3943fef46ecf6fc0a.png