Editorial - Ice-Cream Party
PROBLEM LINK:
Author: Divesh Thakker
Tester: Nishit Patel
Editorialist: Divesh Thakker
Difficulty
Medium
Pre-Requisites
Dynammic Programming
Problem statement
There are n numbers and you have to choose some numbers such that their sum is minimum under the condition: for each i - atleast either i-1, i, or i+1 is chosen.
Quick Explanation
There are 3 options to begin with - taking the 1st one , taking the 2nd one , and taking the 3rd one. Subsequently apply dp on the rest of the array.
Explation
If you choose an element i then u have to choose either i+1, i+2, i+3. Hence we have 3 choices at the start -
-
To take the first element . Then it is not complusary to take the last element as its ajacent element ie. the first element is taken .
-
To take the 2nd element . Then it will be normal dp as it not compulsary to take the last element as 1st element has its ajacent element ie. the 2nd element taken.
-
To take the 3rd element . Then it is compulsary to take the last element as 1st element has no ajacent element taken. Hence we have to compulserly choose the last element . (One tecnique is to add INT_MAX after the last element which will make it nesserary to take the last element)
Subsequently continue on to the dp solution and get the best of these 3 conditions and print that answer.