Problem link: Problem - 698A - Codeforces

I’m new to dynamic programming and I didn’t really understand the editorial. It would be appreciated if someone could explain it along with some code.

Thanks!

Problem link: Problem - 698A - Codeforces

I’m new to dynamic programming and I didn’t really understand the editorial. It would be appreciated if someone could explain it along with some code.

Thanks!

Let dp[i][j] denote the minimum number of days she’ll rest if she did activity j before.

if j is 1, she did a contest, and if j is 2 she went to the gym, and j=0 if she rested

seq[i] is the 0 indexed input. basically stores what she can do on the i+1th day.

```
for(int i=1;i<=n;i++){
dp[i][0]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+1; //she can take a rest, anytime,
// so we take the minimum of all 3 possibilities and add 1 for today's rest
dp[i][1]=1e9;//just set it to a large value
dp[i][2]=1e9;//We'll change it if it's possible
if(seq[i-1]&1){ //if she can do a contest today
dp[i][1]=min(dp[i-1][2],dp[i-1][0]);//minimum of resting yesterday or gyming yesterday
}
if(seq[i-1]&2){//if she can gym today
dp[i][2]=min(dp[i-1][1],dp[i-1][0]);//minimum of resting yesterday or
//giving a contest yesterday
}
}
```

4 Likes