algorithm - C++ 动态规划 : error in traversing the grid

Question

这是一个 question 8来自 2018 AIME Paper :一只 Frog 位于坐标平面的原点。从点(x, y)， Frog 可以跳到点(x + 1, y), (x + 2, y) 、(x, y + 1) 或 (x, y + 2)。找出 Frog 从 (0, 0) 开始到 (x, y) 结束的不同跳跃序列的数量。

感觉可以使用动态规划来解决，但我的代码似乎有错误，我无法调试。这就是我解决问题的方式:

如果 f[i][j] 表示从 (0, 0)< 到达网格点 (i, j) 的方法数然后

f[i][j] = f[i - 1][j] + f[i - 2][j] + f[j - 1][i] + f[j - 2][i]

我们必须为基本情况分配 f[][] 的值..

我不认为逻辑有问题。但是输出很糟糕。 这是我的代码:https://ideone.com/lhhMUL

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    int f[n][n];
    f[0][1] = f[1][0] = 1;
    f[0][2] = f[2][0] = 2;
    f[1][2] = f[2][1] = 5;

    for (int i = 2; i <= x - 1; i++) {
        for (int j = 2; j <= y - 1; j++) {
            f[i][j] = f[i - 1][j]
                      + f[i - 2][j]
                      + f[j - 1][i]
                      + f[j - 2][i];
        }
    }
    cout << f[y][x];

    return 0;
}

Answer 1

我看到的两个错误是

1. j 和 i 在你的递归方程中颠倒了
2. 从不计算 f 的初始值(例如 f[3][1] )。它们只是分配数组时内存中内容的随机值。

#include <bits/stdc++.h>
using namespace std;

int main() 

{
    int n,x,y; cin>>n>>x>>y;
    int f[n][n];
    f[0][0]=1;
    f[1][0]=1;
    f[0][1]=1;
    f[1][1]=2;   

    for(int i = 2; i <= x; i ++ ) {
        f[i][0] = f[i-1][0] + f[i-2][0];
    }
    for(int i = 2; i <= x; i ++ ) {
        f[i][1] = f[i-1][1] + f[i-2][1] + f[i][0];
    }
    for(int j = 2; j <= y; j ++ ) {
        f[0][j] = f[0][j-1] + f[0][j-2];
    }
    for(int j = 2; j <= y; j ++ ) {
        f[1][j] = f[1][j-1] + f[1][j-2] + f[0][j];
    }

    for (int i=2; i<=x; i++)
        for (int j=2; j<=y; j++) {
            f[i][j]=f[i-1][j]+f[i-2][j]+f[i][j-1]+f[i][j-2];
            // cout << i << " " << j << " " << f[i][j] << endl;
        }

    cout<< f[x][y];

    return 0;
}