576. 出界的路径数--java版

本题看了15分钟，不会做，上网搜了一篇文章，思路挺清楚的，递归方式可理解

参考：

https://www.jianshu.com/p/e849c7bb0306

不过是用Python写的，copy了一版java版本的

代码如下：

public class Code576 {

    public int findPaths(int m, int n, int N, int i, int j) {
        return goStepOne(m, n, i, j, N, 0);
    }

    private int goStepOne(int m, int n, int i, int j, int N, int step) {
        if (step >= N) {
            return 0;
        }
        int result = 0;
        step++;
        if (goStepFinal(m, n, i, j, 1)) {
            result++;
        } else {
            result += goStepOne(m, n, i-1, j, N, step);
        }
        System.out.println("result:"+result);

        if (goStepFinal(m, n, i, j, 2)) {
            result++;
        } else {
            result += goStepOne(m, n, i, j+1, N, step);
        }

        if (goStepFinal(m, n, i, j, 3)) {
            result++;
        } else {
            result += goStepOne(m, n, i + 1 , j, N, step);
        }

        if (goStepFinal(m, n, i, j, 4)) {
            result++;
        } else {
            result += goStepOne(m, n, i, j-1, N, step);
        }

        return result;
    }


    private boolean goStepFinal(int m, int n, int i, int j, int direction) {
        System.out.println(m +":" + n+":" + i+":" + j+":" + direction);
        if (direction == 1) {
            return i == 0;
        } else if (direction == 2) {
            return j == n-1;
        } else if (direction == 3) {
            return i == m-1;
        } else {
            return j == 0;
        }
    }

    public static void main(String[] args) {
        Code576 code576 = new Code576();
        System.out.println("输入: m = 2, n = 2, N = 2, i = 0, j = 0 \n " + code576.findPaths(2,2,2,0, 0));
        System.out.println("输入: m = 1, n = 3, N = 3, i = 0, j = 1 \n " + code576.findPaths(1,3,3,0, 1));
        StopWatch stopWatch = new StopWatch("hello");
        stopWatch.start("耗时");
        code576.findPaths(1,3,3,0, 1);
        stopWatch.stop();
        System.out.println("输入: m = 8, n = 7, N = 16, i = 1, j = 5 \n " + stopWatch);
    }

使用计分板可以解决性能问题，但是算法本身是错的89个用例过不了

动态规划来解决
https://blog.csdn.net/baidu_37107022/article/details/73188963