×

Codeforces DP problem explanation

 0 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 asked 31 Dec '18, 00:23 1 accept rate: 0%

 0 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]); } } } dp[n][3]; //Answer to the problem  answered 10 Feb, 13:28 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,170
×682
×26

question asked: 31 Dec '18, 00:23

question was seen: 229 times

last updated: 10 Feb, 13:28