0

動的計画法を使用して格子パスの問題を解決しようとしていました。

22 グリッドの左上隅から開始して、右下隅まで (バックトラックなしで) 6 つのルートがあります。

ルート

2020 年のグリッドを通過するルートはいくつありますか?

この質問を解決するために私が書いたコードは次のとおりです。どこが間違っていますか。毎回間違った出力が得られるようです。変数データ型のいくつかの境界を越えていますか?

#include <stdio.h>
int count = 0;
int limita,limitb;
long long int cache[20][20];
unsigned long long int start(int a,int b)
{
    unsigned int long long i = 0;
    if(a == limita && b == limitb)
        return 1;
    if(cache[a][b] != -1)
        return cache[a][b];
    if(a != limita)
        i += start(a+1, b);
    if(b != limitb)
        i += start(a, b+1);
    cache[a][b] = i;
    return i;
}
int main(void)
{
    limita = limitb = 19;
    int i,j;
    for(i = 0; i < 20; i++)
        for(j = 0; j <20;j++)
            cache[i][j] = -1;
    unsigned long long int number = start(0,0);
    printf("The number of ways to reach the end is %llu\n",number);
    return 0;
}

私を助けてください

4

1 に答える 1

3

サイズ 1*1 のグリッド:

    0    1
   0+-----+
    |     |
    |     |
   1+-----+
    |<-2->|

サイズ 2*2 のグリッド:

    0    1    2
   0+----+----+
    |    |    |
    |    |    |
   1+----+----+
    |    |    |
    |    |    |
   2+----+----+
    |<---3--->|

...

あなたのアルゴリズムは問題ないようですが、エッジのカウントが間違っています。

于 2012-09-17T07:37:57.430 に答える