[解決済み] 0と1の行列のパスの総数を求めよ

質問

という内容のプログラムを作っています。

M行N列の2次元行列が与えられ、最初は配列の左上のセルである(0,0)に配置される。あなたは、右にも下にも移動することができます。配列は1と0で埋め尽くされている。1 はそのセル内を移動できることを示し、0 はそのセル内を移動できないことを示す。左上のセルから右下のセルへの移動経路の数を返せ。答えが大きくなる可能性があるので、ans%(10^9+7)を返す必要がある。

私はそれを実装しようとし、いくつかのシナリオで動作しているが、いくつかのケースでは失敗している。

static int count(int a[][], int i, int j) {
    int rows = a.length;
    int cols = a[0].length;
    if(a[i][j] == 0)  return 0;
    if (i == rows - 1 && j == cols - 1)
        return a[i][j];
    else if (i == rows - 1)
        return a[i][j + 1];
    else if (j == cols - 1)
        return a[i + 1][j];
    else if (a[i][j] == 1)
        return count(a, i + 1, j) + count(a, i, j + 1);
    else
        return 0;
}

以下の配列の場合、失敗します。 {{1,1}, {0,1}}

このプログラムの何が問題なのか、教えてください。

アップデートしてください。

Johnny Moppさん、ありがとうございます！上記のテストケースは解決しました。このプログラムのパフォーマンスを向上させるにはどうしたらよいでしょうか？

解決方法は？

をチェックする必要があります。 a[i][j] . 0なら0を返します。

また、パフォーマンスについてですが、この方法で書かれたアルゴリズムは、同じ値を何度も計算するため、非常に遅くなります。暗記（2つ目の配列を作成し、返す値をすべて保存し、関数の最初に未計算の値をチェックする）するか、ダイナミックプログラミングで解決してください。

EDIT: modulo 10^9+7を忘れていますよ。

2回目の編集（コメントへの返信）。 そんな感じでしょうか。3つのループに分けることで、メイン（3番目）のループの演算量を減らし、ビッグデータに対してかなり高速な関数になるようにしました。また、計算の方向を変えていますが、これは全く重要ではありません。

static int count_dp(int a[][]){
    int rows = a.length;
    int cols = a[0].length;
    int[][] dp = new int[rows][cols];

    dp[0][0] = a[0][0];

    for(int i=1;i<rows;i++)
        if(dp[i-1][0]==1 && a[i][0]==1)
            dp[i][0] = 1;

    for(int i=1;i<cols;i++)
        if(dp[0][i-1]==1 && a[0][i]==1)
            dp[0][i] = 1;

    for(int i=1;i<rows;i++)
        for(int j=1;j<cols;j++)
            if(a[i][j]==1)
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000007;

    return dp[rows-1][cols-1];
}