Hi,
in the hints of the assignment notebook wrt Dynamic Programming fcn, it’s stated to check source[i]==target[j],
but shouldn’t it be source[i-1]==target[j-1] ?
Hi, Fabian.
If I understand your question correctly, then in the HINTS (as in text part of Part 4.1 Dynamic Programming) it shouldn’t - the text is correct:
- You do not add replacement cost if source[row] == target[column]. For example in words ‘stay’ and ‘play’ letters in position say 2 are equal (both are ‘a’) - in this case you do not add replacement cost of 2.
- You do add replacement cost if source[row] != target[column]. For example in words ‘stay’ and ‘play’ letters in position say 1 are not equal (‘t’ and ‘l’ respectively) - in this case you do add replacement cost of 2.
But maybe your doubts come from your code in # UNQ_C11:
- where D matrix is with extra row and column - #initialize cost matrix with zeros and dimensions (m+1,n+1)
- and you loop through rows - # Loop through row 1 to row m, both inclusive
- and you loop through columns - # Loop through column 1 to column n, both inclusive
So in this case your loops start from 1, but string indexing (of both source and target) starts from 0 and you have to compensate for that and this might explain your confusion?