# Codeforces DP problem explanation

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?

https://codeforces.com/contest/1096/problem/D

Here we can memoize our solution in the DP array, let dp[i][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[i][0] = dp[i-1][0] + cost[i].

If the ith character of our string is βaβ then dp[i][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[i].

Similarly, If the ith character of our string is βrβ then dp[i][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[i].

Similarly for βdβ we have dp[i][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[i][j] = dp[i-1][j];

if(arr[i] == 'h'){
dp[i][0] = dp[i-1][0] + cost[i];
}
else if(arr[i] == 'a'){
dp[i][1] = min(dp[i-1][0], dp[i-1][1] + cost[i]);
}
else if(arr[i] == 'r'){
dp[i][2] = min(dp[i-1][1],dp[i-1][2] + cost[i]);
}
else if(arr[i] == 'd'){
dp[i][3] = min(dp[i-1][2],dp[i-1][3] + cost[i]);
}
}
}