i was trying to solve this DP problem … i guessed the state … dp[i][j]-> minimum cost when our first finger is at index I and second finger is at index j… i am not getting how to write the relation with previous state?? can anyone help plzzzzzz???
1 Like
I think the states would be, dp[idx][i][j]. Idx is the idx of the letter of the string you’re currently at and ‘i’ is the position of first finger and ‘j’ is the position of the second finger.
dp[idx][i][j]= min( cost(i,k) + dp[idx+1][k][j], cost(j,k) + dp[idx+1][i][k])
cost(i,k) is the cost function to type letter at kth positon when finger is at ith idx.