strange bug causes TLE !

Правка en1, от X-O__O-X, 2021-03-20 22:47:45

I was solving the problem: coin combination II from CSES. https://cses.fi/problemset/task/1636/

My solution leads to TLE.

#include <bits/stdc++.h> 
using namespace std; 
 
 
int 
main() {
 
    int mod = 1e9+7;
	int n, x; 
    cin>>n>>x; 
    vector<int> c(n);
    for (int &a : c) cin >> a;
 
    vector<vector<int>> dp(x+1,vector<int>(n+1,0));
    dp[0][0] = 1;
    for (int i = 0; i <= x; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i][j-1]; 
            int up = i - c[j-1]; 
            if (up >= 0)
            {
                (dp[i][j] += dp[up][j]) %= mod; 
            }
        }
    }
    cout << dp[x][n] << endl;
}

But solution in this editorial leads to AC..

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

int main() {
  int mod = 1e9+7;
  int n, target;
  cin >> n >> target;
  vector<int> x(n);
  for (int&v : x) cin >> v;

  vector<vector<int>> dp(n+1,vector<int>(target+1,0));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= target; j++) {
      dp[i][j] = dp[i-1][j];
      int left = j-x[i-1];
      if (left >= 0) {
	(dp[i][j] += dp[i][left]) %= mod;
      }
    }
  }
  cout << dp[n][target] << endl;
}

The only difference I see is the why the DP table is set.. and consequently the way in which we compute it.

in my solution, dp[i][j] => number of ways to make sum i using first j coins.

in editorial solution, dp[i][j] => number of ways to make sum j using first i coins.

but, the number of iterations is exactly the same..

any explanations ?

thanks

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский X-O__O-X 2021-03-20 22:47:45 1734 Initial revision (published)