leetcode 576. Out of Boundary Paths K步内出界的次数之和 + DP动态规划

约定不等于承诺〃 2022-06-03 04:39 112阅读 0赞

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:  
Input:m = 2, n = 2, N = 2, i = 0, j = 0  
Output: 6  
Explanation:  
![这里写图片描述][SouthEast]

Example 2:  
Input:m = 1, n = 3, N = 3, i = 0, j = 1  
Output: 12  
Explanation:  
![这里写图片描述][SouthEast 1]

Note:  
Once you move the ball out of boundary, you cannot move it back.  
The length and height of the grid is in range \[1,50\].  
N is in range \[0,50\].

本题题意很简单，直接使用DFS肯定会超时，现实切确会超时，感觉应该是可以有DP的做法的，但是自己还是不会做，所以网上找了一个做法

使用一个三维的DP数组，其中dp\[k\]\[i\]\[j\]表示总共走k步，从(i,j)位置走出边界的总路径数。那么我们来找递推式，对于dp\[k\]\[i\]\[j\]，走k步出边界的总路径数等于其周围四个位置的走k-1步出边界的总路径数之和，如果周围某个位置已经出边界了，那么就直接加上1，否则就在dp数组中找出该值，这样整个更新下来，我们就能得出每一个位置走任意步数的出界路径数了，最后只要返回dp\[N\]\[i\]\[j\]就是所求结果了，

需要注意的是使用long long类型，要不然会整数越界导致错误答案

建议和[leetcode 688. Knight Probability in Chessboard 动态规划DP + 很棒的做法][leetcode 688. Knight Probability in Chessboard _DP _] 一起学习

**这道题需要注意的地方就是使用long long数据来避免int的数据越界**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    class Solution
    {
    public:
    
        int findPaths(int m, int n, int N, int i, int j)
        {
            vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));
            for (int k = 1; k <= N; k++)
            {
                for (int x = 0; x < m; x++)
                {
                    for (int y = 0; y < n; y++)
                    {
                        long long v1 = (x == 0) ? 1 : dp[k - 1][x - 1][y];
                        long long v2 = (x == m-1) ? 1 : dp[k - 1][x + 1][y];
                        long long v3 = (y == 0) ? 1 : dp[k - 1][x][y - 1];
                        long long v4 = (y == n-1) ? 1 : dp[k - 1][x][y + 1];
                        dp[k][x][y]=(v1+v2+v3+v4) % 1000000007;
                    }
                }
            }
            return dp[N][i][j];
        }
    
    
        int count = 0;
        int findPathsByDFS(int m, int n, int N, int i, int j) 
        {
            dfs(i, j, m, n, N);
            return count;
        }
    
        void dfs(int x, int y, int row, int col, int Len)
        {
            if (x < 0 || x >= row || y < 0 || y >= col)
            {
                count = (count + 1) % 1000000007;
                return;
            }
            else
            {
                if (Len > 0)
                {
                    dfs(x - 1, y, row, col, Len - 1);
                    dfs(x + 1, y, row, col, Len - 1);
                    dfs(x, y - 1, row, col, Len - 1);
                    dfs(x, y + 1, row, col, Len - 1);
                }
            }
        }
    };

[SouthEast]: /images/20220603/ac8f06b2cd924facb240232e5a41efd1.png
[SouthEast 1]: /images/20220603/a06bcf04a52549da866d651a25e88adb.png
[leetcode 688. Knight Probability in Chessboard _DP _]: http://blog.csdn.net/jackzhang_123/article/details/78883658