Блог пользователя ProveMeRight

Автор ProveMeRight, история, 3 года назад, По-английски

I was solving the CSES Dynamic Programming Problem named Coin Combinations I. I don't know what's the matter here.

In my view, Both the commented code, as well as uncommented code, is the same. But The uncommented code is throwing TLE and the Commented Code is passing all the test cases.

This is the code

vi dp(1000001, 0);
vi v(1000001, 0);
void solve() {
  int n, x;
  cin >> n >> x;
  FOR(i, 0, n) cin >> v[i];



  // for(int i =0;i<=x;i++)
  //   {
  //       // base case
  //       if(i==0)
  //       {
  //           dp[i] = 1;
  //       }
  //       else
  //       {   dp[i] = 0;
  //           for(int j = 0;j<n;j++)
  //           {
  //               if(i-v[j]>=0)
  //               dp[i] += dp[i-v[j]];
  //           }
  //           dp[i] %= mod;
  //       }
  //   }

  for(int i =0;i<=x;i++)
  {
    if (i == 0)
    {
      dp[i] = 1;
    }
    else
    {
      dp[i] = 0;
      for(int j = 0;j<n;j++)
      {
        if (i - v[j] >= 0)
        {
          dp[i] += dp[i - v[j]];
        }
        dp[i] %= mod;
      }
    }
  }

  cout << dp[x] << endl;
}

Please Help Me. Thank you.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

It's not the same. Check your inner for loop. dp[i] %= mod is inside for loop in the uncommented code and outside the loop in commented code.