here is the question
there are n shops in a row. You have a number of coins to spend while
shopping. These coins are denoted by c1,c2,…cn where Ci is the number of
coins that you have to spend when you shop at the ith shop.
you start shopping from the very first shop and move towards the nth shop sequentially
For every shop that you skip, you have to buy one candy. Each candy costs x coins. You cannot skip
more than three shops in a row. Also you cannot skip first and last shop.
your task is to determine the minimum number of coins that you have spent after shopping
from the nth shop.
Constraints
2<= n <= 2x10^5
1<= x , Ci <= 2x10^5
If you know any similar questions like this please mention the links.
1 Like
The recurrence relation is as follows :
dp[i] = c[i] + min(dp[i-1],x+dp[i-2],2*x+dp[i-3],3*x+dp[i-4]);
Run a for loop for the same and dp[n] should be your final answer.
1 Like
I think it would not consider the condition
" You cannot skip more than three shops"
That’s the problem.
I think you have problem with understanding the dp-relation here. Its clearly handled here. You can either skip 0-shop, in that case, answer is c[i] + dp[i-1], if you are skip 1-shop, answer is c[i]+ x+dp[i-2] , and so on , for skipping 2/3 shops. Take minimum of all those cases and you have your answer
I hope it isn’t an ongoing contest problem because this Question was asked in one of previous coding tests and companies sometimes repeat questions.
1 Like
Should I delete my answer ? (But it seems OP is trying to understand it/not copying)
Maybe we should wait for his response…why is he asking this problem!
1 Like
It is the problem from on campus coding round which was held in early morning and finished at 9 AM.
I have no problem in deleting the post if community suggests.
Okay! Then it’s not an issue.
How to initialize dp 0 1 2 3 4 values ?
Can you pls tell?
As we are using dp[i-1] … dp[i-4].
So pls tell the initialization of first 4 values of dp array?
Hey , how to initialize dp 0 1 2 3 4 values ?
https://leetcode.com/problems/min-cost-climbing-stairs/
Give a try to the question above and do not forget to look at the “Discuss” section of the same. Some users there have beautifully explained tips and tricks of dynamic programming.