CODEWITHSUNDEEP
algorithmdynamic-programming
Mathejunior
Mathejunior

Reputation: 153

C++ Dynamic Programming: error in traversing the grid

Here's a question 8 from 2018 AIME Paper : A frog is positioned at the origin of the coordinate plane. From the point (x, y), the frog can jump to any of the points (x + 1, y), (x + 2, y), (x, y + 1), or (x, y + 2). Find the number of distinct sequences of jumps in which the frog begins at (0, 0) and ends at (x, y).

It felt that it can be solved using dynamic programming but my code seems to have an error which I cannot debug. This is how I approached the problem:

If f[i][j] denotes the number of ways to reach grid-point (i, j) from (0, 0) then

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

and we have to assign values of f[][] for the base cases..

I don't think there's an issue with the logic. But the outputs are terrible. Here's my code : 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;
}

Upvotes: 0

Views: 313

Answers (1)

Mark Wistrom
Mark Wistrom

Reputation: 161

Two bugs I see are

  1. j and i are reversed in your recursion equation
  2. Initial values of f (for example f[3][1] ) are never calculated. They are just random values of what was in memory when the arrays were allocated.
#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;
}

Upvotes: 2

Related Questions