HackerEarth Big P and The Road Less Travelled problem solution

In this HackerEarth Big P and The Road Less Travelled problem solution Big P is willing to climb up a hill. The hill is divided into several checkpoints where the travelers can buy water,food etc for their trip.

At each checkpoint there are several roads that go up to other checkpoints (Not necessarily the next checkpoint).

Now Big P is standing at the base of the hill i.e at checkpoint 1 and wants to know the total number of ways he could climb to the top of the hill i.e the last checkpoint N.

HackerEarth Big P and The Road Less Travelled problem solution.

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class TestClass
{
    static int n;
    static int[] paths; 
    static int numPaths = 0;
    static int[] startingPts;
    static int[] endingPts;

    public static void main (String[] args)
    {

  Scanner f = new Scanner(System.in);
  n = f.nextInt ();
  paths = new int [n + 1];
  for (int i = 0 ; i < n + 1 ; i++)
      paths [i] = -1;
  startingPts = new int [1000000];
  endingPts = new int [1000000];
  numPaths = 0;
  int x = f.nextInt ();
  int y = f.nextInt ();
  while (!(x == 0 && y == 0))
  {
      startingPts[numPaths] = x;
      endingPts[numPaths] = y;
      numPaths++;
      x = f.nextInt ();
      y = f.nextInt ();
  }
  System.out.println (findNumPaths (1));
    }
    static public int findNumPaths (int pt)
    {
  if (pt == n)
      return 1;
  else
  {
      int sum = 0;
      for (int i = 0 ; i < numPaths ; i++)
      {
    if (startingPts [i] == pt)
    {
        int answer = paths [endingPts [i]];
        if (answer != -1)
      sum += answer;
        else
        {
      int a = findNumPaths (endingPts [i]);
      paths [endingPts [i]] = a;
      sum += a;
        }
    }
      }
      return sum;
  }
    }
}

Second solution

#include <bits/stdc++.h>

using namespace std;

vector <int> v[100005];
int n;
long long dp[100005];
bool vis[100005];

long long f(int idx)
{
  if ( idx == n ) return 1;
  if ( vis[idx] ) return dp[idx];
  vis[idx] = true;
  long long ans = 0;
  for ( int i = 0; i < v[idx].size(); i++ ) ans += f(v[idx][i]);
  dp[idx] = ans;
  return ans;
}

int main()
{
  int x,y;
  cin >> n;
  for ( ;; ) {
    cin >> x >> y;
    if ( x == 0 && y == 0 ) break;
    v[x].push_back(y);
  }
  long long ans = f(1);
  cout << ans << endl;
    return 0;
}

coding problems solutions