How to solve this LeetCode Dp Problem ?

Question

Link to the problem : https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/

Answer 1

Let me make it easy for you

Let , there be dp[i][j][k] , which means , that is the best answer for string of length k .

We have assumed that we have solved the question if length of string was 'k'

dp[i][j][k] means the best answer for a string of length ‘k’ , where first finger is on character 'i' and second finger is on character 'j'

Example string :

aab

dp[a][b][3] means , the best answer for the string if finger “1” is on “a”(we don’t care about on which “a” it was) and finger “2” is on “b” in the final position .

How to find the answer for dp[i1][j1][k+1] ?

If we can do this, we are done .

Answer for string of length “k+1” depends on “k”

Option-1 : dp[u][j1][k] + cost to go from character “u” to character “i1”

(we will try each character “u” (a/b/c/d/e/…z) for option-1 .

Option-2 : dp[i1][v][k] + cost to go from character “v” to character “j1”

(we will try each character “v” (a/b/c/d/e/…z) for option-2 .

Finally ,

dp[i1][j1][k+1] = Minimum(Option-1,Option-2) .

Hence the problem can be solved in O(26*26*N)

If string is of length “N”, final answer is minimum(dp[a][a][N],dp[a][b][N],dp[a][c][N]…dp[z][z][N])

Hope it helps!!!