title: Find minimum cost of tickets
body: <p>Find minimum cost of tickets required to buy for traveling on known days of the month (1...30). Three types of tickets are available : 1-day ticket valid for 1 days and costs 2 units, 7-days ticket valid for 7 days and costs 7 units, 30-days ticket valid for 30 days and costs 25 units. </p>
  
  <p>For eg: I want to travel on [1,4,6,7,28,30] days of the month i.e. 1st, 4th, 6th ... day of the month. How to buy tickets so that the cost is minimum.</p>
  
  <p>I tried to use dynamic programming to solve this but the solution is not giving me the correct answer for all cases. Here is my solution in Java : </p>
  
  <pre><code>public class TicketsCost {
      public static void main(String args[]){
          int[] arr  =  {1,5,6,9,28,30};
          System.out.println(findMinCost(arr));
      }
      public static int findMinCost(int[] arr) {
          int[][] dp = new int[arr.length][3];
          int[] tDays = {1,7,30};
          int[] tCost = {2,7,25};
  
          for (int i = 0; i &lt; arr.length; i++) {
              for (int j = 0; j &lt; 3; j++) {
                  if (j==0){
                      dp[i][j]= (i+1)*tCost[j];
                  }
                  else{
                      int c = arr[i]-tDays[j];
                      int tempCost = tCost[j];
                      int k;
                      if (c&gt;=arr[0] &amp;&amp; i&gt;0){
                          for (k = i-1; k &gt;= 0; k--) {
                              if (arr[k]&lt;=c){
                                  c = arr[k];
                              }
                          }
                          tempCost += dp[c][j];
                          int tempCostX =  dp[i-1][j] + tCost[0];
                          tempCost = Math.min(tempCost,tempCostX);
  
                      }
                      dp[i][j] = Math.min(tempCost,dp[i][j-1]);
                  }
              }
          }
          return dp[arr.length-1][2];
      }
  }
  </code></pre>
  
  <p>The solution doesn't work for {1,7,8,9,10} input, it gives 10 but the correct answer should be 9. Also, for {1,7,8,9,10,15} it give 13 but the correct is 11. 
  I have posted my solution not for other to debug it for me but just for reference. I was taken a bottom-up dynamic programming approach for this problem. Is this approach correct?</p>