I am fairly new to dp and practicing to get better. Can anyone explain this problem from codeforces educational round. There is an editorial but still I am not convinced with the intution. Can anyone help me explain it?

# Codeforces DP problem explanation

**ayush1111**#2

Here we can memoize our solution in the DP array, let dp*[4] be the cost of making the string **easy** the index till 1<=i<=N where ith character can be any character of “hard”.

If the ith character of our string is ‘h’ then dp*[0] = dp[i-1][0] + cost*.

If the ith character of our string is ‘a’ then dp*[1] = we have 2 options whether to take dp[i-1][0] i.e. cost of making string **easy** removing only character ‘h’ or second option is to add the current cost of ‘a’ to the previously calculated cost of ‘a’ i.e. dp[i-1][1] + cost*.

Similarly, If the ith character of our string is ‘r’ then dp*[2] = we have 2 options whether to take dp[i-1][1] i.e. cost of making string **easy** removing only character ‘a’ or second option is to add the cost of ‘r’ to the previously calculated cost of ‘r’ i.e. dp[i-1][2] + cost*.

Similarly for ‘d’ we have dp*[3] = minimum of dp[i-1][2] // Taking only cost till first i-1 index and having character ‘r’ or take dp[i-1][3] i.e. adding ‘d’ cost into in the previous calculated cost of ‘d’.

```
for(int i = 1; i <= n; i++){
for(int j = 0; j < 4; j++){
dp*[j] = dp[i-1][j];
if(arr* == 'h'){
dp*[0] = dp[i-1][0] + cost*;
}
else if(arr* == 'a'){
dp*[1] = min(dp[i-1][0], dp[i-1][1] + cost*);
}
else if(arr* == 'r'){
dp*[2] = min(dp[i-1][1],dp[i-1][2] + cost*);
}
else if(arr* == 'd'){
dp*[3] = min(dp[i-1][2],dp[i-1][3] + cost*);
}
}
}
dp[n][3]; //Answer to the problem
```