title: Book Shop Question (same logic but 2 different implementation)
body: <p>You are in a book shop which sells n different books. You know the price and number of pages of each book.</p>
  <p>You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.</p>
  <p>So i figured that it was an example of 0-1 knapsack problem.</p>
  <p>In my first approach I created a dp array as <strong>dp[i][j] which tells us the maximum pages using i money and first j books.</strong></p>
  <pre><code>    int n,budget;
      cin&gt;&gt;n&gt;&gt;budget;
      vector&lt;int&gt; price(n),pages(n);
      for (int &amp;v : price)
          cin &gt;&gt; v;
      for (int &amp;v : pages)
          cin &gt;&gt; v;
      
      vector&lt;vector&lt;int&gt; &gt; dp(budget+1 , vector&lt;int&gt;(n+1,0));
  
      for(int i=1 ; i&lt;budget+1 ; i++){
          for(int j=1; j&lt;n+1 ; j++){
              if(i-price[j-1] &gt;= 0){
                  dp[i][j] = max(dp[i][j-1] , dp[i-price[j-1]][j-1] + pages[j-1]);
              }
              else{
                  dp[i][j] = dp[i][j-1];
              }
          }
      }
      cout&lt;&lt;dp[budget][n];
  </code></pre>
  <p>But the problem is that this solution exceeds the time limit.</p>
  <p>The solution posted on the site had the same logic but the rows and columns of dp vector were flipped.That is <strong>dp[i][j] tells the maximum number of pages using j money and first i books</strong>. The solution was way faster.</p>
  <pre><code>    int n,x;
      cin&gt;&gt;n&gt;&gt;x;
      vector&lt;int&gt; price(n), pages(n);
  
      for (int &amp;v : price)
          cin &gt;&gt; v;
      for (int &amp;v : pages)
          cin &gt;&gt; v;
  
      vector&lt;vector&lt;int&gt; &gt; dp(n + 1, vector&lt;int&gt;(x + 1, 0));
      for (int i = 1; i &lt;= n; i++)
      {
          for (int j = 1; j &lt;= x; j++)
          {
              if (j - price[i - 1] &gt;= 0)
              {
                  dp[i][j] = max(dp[i-1][j], dp[i - 1][j - price[i - 1]] + pages[i - 1]);
              }
              else{
                  dp[i][j] = dp[i-1][j];
              }
          }
      }
      cout &lt;&lt; dp[n][x] &lt;&lt; endl;
  </code></pre>
  <p>I don't understand why there is a difference in time for the above implementations. I am new to competitive programming so please clarify my doubt.
  Thanks in advance.</p>