欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

出界的路径数

程序员文章站 2022-07-15 11:37:23
...

一、题目描述

题目链接:https://leetcode-cn.com/problems/out-of-boundary-paths/

出界的路径数

 

二、题目分析

经典记忆搜索,题解参考:https://leetcode-cn.com/problems/out-of-boundary-paths/solution/ji-yi-hua-di-gui-chao-jian-ji-by-pwrliang/

 

三、代码

    private int[] dirs = {0,1,0,-1,0};
    public int findPaths(int m, int n, int N, int i, int j) {
        Integer[][][] memo = new Integer[m][n][N+1];
        return dfs(m,n,memo,N,i,j);
    }

    private int dfs(int m, int n, Integer[][][] memo, int N, int i, int j) {
        if (N < 0) return 0;
        if (i < 0 || i == m || j < 0 || j == n) return 1;
        if (memo[i][j][N] != null) return memo[i][j][N];
        int sum = 0;
        for (int k = 0; k < 4; ++k) {
            sum = (int) (((long)sum + dfs(m,n,memo,N-1,i+dirs[k],j+dirs[k+1])) % 1000000007);
        }
        memo[i][j][N] = sum;
        return sum;
    }