请教一道算法题目

各位学哥学姐好，我想请问一道算法题目是：
给定M*N矩阵 从（0，0）走到（0，N-1） 只能向右上、右、右下走 问总共有多少种走法

follow up是中间必须经过点（x，y).

我感觉这个题要用DP做，但是不清楚DP的两个for循环范围是什么，follow up怎么做，求学长学姐指教，谢谢

只能向右走，就一列一列地更新你的dp矩阵。第一列除了原点是1其他都是0，其他点都是其左边三个点的和。follow up就是分两半，先算(0,0)到(x,y)的走法a，再算(x,y)到终点的走法b，结果就是a*b

beetle 发表于 2018-1-20 01:20
只能向右走，就一列一列地更新你的dp矩阵。第一列除了原点是1其他都是0，其他点都是其左边三个点的和。foll ...

就是这样 space的话用一列 M size 就可以了

zhuxinyi2017 发表于 2018-1-20 02:36
就是这样 space的话用一列 M size 就可以了

您好，请问这里不能只用一维DP吧，因为X和Y方向都要变化。

beetle 发表于 2018-1-20 01:20
只能向右走，就一列一列地更新你的dp矩阵。第一列除了原点是1其他都是0，其他点都是其左边三个点的和。foll ...

您好，我还是不太理解您的意思，能贴一段伪代码么，或者您看看我写的这个dp，还是不太清楚，谢谢您。

public class Solution {
        public int NumberofPath(int[][] matrix){
                int[][] dp = new int[matrix.length][matrix[0].length + 1];
                matrix[0][0] = 1;
                for (int i = 1; i < matrix.length; i++){
                        for (int j = 1; j < matrix[0].length; j++){
                                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + dp[i - 1][j + 1];
                        }
                }
                return dp[0][matrix[0].length];
        }
}

wjw779 发表于 2018-1-20 06:05
您好，我还是不太理解您的意思，能贴一段伪代码么，或者您看看我写的这个dp，还是不太清楚，谢谢您。

...

我觉得可以用两列，因为对于当前这个点，他可以从三个方向来，左上，左下和左边，所以每次可以用第一列保存前一列的值，更新到第二列上，循环结束以后把第二列换到第一列就行了，或者直接用(j%2)和（j-1）%2来看用第几列

bear3488 发表于 2018-1-20 08:15
我觉得可以用两列，因为对于当前这个点，他可以从三个方向来，左上，左下和左边，所以每次可以用第一列保 ...

求层主贴一段代码，DP还是不太清楚

wjw779 发表于 2018-1-20 06:04
您好，请问这里不能只用一维DP吧，因为X和Y方向都要变化。

一列就够了,  你每次必须往右走一步的，右，右上，右下，无非是dp 的话要多用几个constant space，出了区域才能update。你update 一个position 必须要在 处理到这个位置加2的地方才可以，这样不会冲突，多用几个variable 记录一下就可以了。