Problem 3. Thirsty Tourist

We will define dp[i][j] = Minimum possible cost if tourists are currently present at the ith shop and left with j litre of water

and our answer will be dp[lastShop][length of journey - dist[lastShop]];

And now we have to think of transitions in our DP definitions. Let's break this into cases.

Case 1). The j litre which is present at the ith shop may be carried forward from any of {0, 1, ... i - 1} shop.

dp[i][j] = min(dp[i][j], dp[i - 1][j + (dist[i] - dist[i - 1])]);

because if we have j + (dist[i] - dist[i - 1]) litre of water at the shop i - 1 then we can left with j litre of water at ith shop.

and since by definition dp[i - 1][j + dist[i] - dist[i - 1]] is the minimum possible cost to have j + dist[i] - dist[i - 1] litre of water at the i - 1 th shop

But this case may or may not be feasible as the capacity c can easily be less than < (j + dist[i] - dist[i - 1]) which is the amount of water we want to be present at i - 1 shop. So we have to go with another case.

Case 2). If we are not able to bring j litre from the any of {0, 1, ... i - 1} because of capacity barrier.

We can think to buy this complete j litre at the cur shop i.e ith shop

dp[i][j] = min(dp[i][j], dp[i - 1][dist[i] - dist[i - 1]] + j * cost[i]);

here we are starting at the i - 1 th shop and carrying exactly the water that is required i.e dist[i] - dist[i - 1] and endup with 0 litre of water at the ith shop and buy the remaining j litre at the current shop i.e i that's why we add the j * cost[i];

But is this the last case ? No it's not. If we can't end with carrying exactly j litre from any of {0, 1, ... , i - 1} shop

Case 3).

Can't we end with any lesser that j i.e{ 1, 2, ... , j - 1} litre and remaining {j - 1, j - 2, .... 1 } [pairwise with first list] we can purchase on the ith shop itself.

so what we can do here

dp[i][j] = min(dp[i][j], dp[i][j - 1] + cost[i]);

we find what is the minimum possible cost to have j - 1 litre of water at the ith shop and then remaining 1 litre I purchase on the current shop (It can also happen that j - 1 litre is also filled in the current shop because the min of case 1. and case 2. is taken)

## Code in C++;

Link : "Click Here":https://github.com/souraavv/NPTEL-DAA-Programming-Assignment-Solutions/blob/master/Week%207%20Programming%20Assignment/ThirstyTourist.cpp

Date Added: 29-04-2021

Sourav Sharma