This problem can be solved with either backtracking/recursion or dynamic programming (optimized backtracking). Instead of just writing code, I will elaborate how I did it briefly.

As with any backtracking problem, you first need to figure out what are your choices. For each of those choices, do the following:

Make that choice
Explore it (the recursive step)
Un-choose (explore the other options)

For this problem, we can first forget about the 30-day ticket that costs 25. It is for buying for the whole month, so it makes sense to minimize our cost with 1-day and 7-day tickets. Then compare the outcome with buying 30-day ticket.

So we have two choices each time: Buy a one day ticket and pay 2 or buy a 7-day ticket and pay 7. I will do this from left to right in my array.

Backtracking Approach

public void MinimumCostOfTickets()
{
int[] A = { 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 29, 30 };
int res = MinTicketCostHelper(A, 0);
res = Math.Min(res, 25); //for buying a ticket for the whole month
Console.WriteLine(res);
}
private int MinTicketCostHelper(int[] A, int index)
{
if (index >= A.Length)
return 0;
///choices we have area:
/// 1. buy a 1-day ticket that costs 2
/// 2. buy a 7-day-consecutive ticket that costs 7
/// for each of those choices
/// choose
/// explore
/// unchoose
///
int oneDayTicketCost = 2 + MinTicketCostHelper(A, index + 1);
//if we want to buy seven day ticket, go until X + 6 since they must be consecutive
int sevenDayTicketIndex = index + 1;
while (sevenDayTicketIndex < A.Length && A[sevenDayTicketIndex] <= A[index] + 6)
sevenDayTicketIndex++;
int seveDayTicketCost = 7 + MinTicketCostHelper(A, sevenDayTicketIndex);
return Math.Min(oneDayTicketCost, seveDayTicketCost);
}

Dynamic Programming Approach

This problem has overlapping sub-problems. If you print out the index parameter, you will see that for a certain day, it is computed many times. You can obviously cache that with a 1D memoization array. You can also invert the problem and do it backwards. This is the same except that we start from the back and try to find out what we have chosen earlier. This is the dynamic programming approach.

public void MinimumCostOfTickets()
{
int[] A = { 1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 29, 30 };
int res = MinCostWithDP(A);
res = Math.Min(res, 25); //for buying a ticket for the whole month
Console.WriteLine(res);
}
private int MinCostWithDP(int[] A)
{
int[] dp = new int[A.Length];
dp[0] = 2;
for (int i = 1; i < A.Length; i++)
{
int oneDay = 2 + dp[i - 1];
int j = i - 1; //find the day before being able to buy a 7-day ticket
while (j >= 0 && A[j] >= A[i] - 6)
j--;
int sevenDay = 7;
if (j >= 0)
sevenDay += dp[j];
dp[i] = Math.Min(oneDay, sevenDay);
}
return dp[dp.Length - 1];
}

Potential Optimizations

We can surely do binary search instead of that while loop to find the X + 6 day. But since our input size is very small (30 days max), it doesn't really make much difference.

If you want to further understand it, try to make the backtracking solution backwards (it is currently computing the result forwards). You will then naturally come to the dynamic programming approach.

Let me know if there is any bug or typo. Hope this helps someone.