# Solution explaining how to approach the DP solution from a recurrence pattern in Java

• The first rule of DP is to establish a recurrence relationship so that no guess work is involved with the E-table. If you have done Levenshtein Distance (Edit distance) algo before, here is the quick thought on using recursion:

``````private int helper(String s1, String s2,int i, int j) {
if(i==s1.length()) {
return s2.length()-j;
}
else if(j==s2.length()) {
return s1.length()-i;
}

if(s1.charAt(i)==s2.charAt(j)) {
return helper(s1,s2,i+1,j+1);
}
else {
return 1+Math.min(helper(s1,s2,i+1,j),helper(s1,s2,i,j+1));
}

}
``````

However, as expected, it will time out :). Now, the idea is to leverage the above and using a top-bottom memoization-based DP to cache the results for reuse. Here is the code for that:

`````` public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int[] r : dp) {
Arrays.fill(r,-1);
}
return helper_dp(word1,word2,0,0,dp);
}
private int helper_dp(String s1, String s2,int i, int j,int[][] dp) {
if(i==s1.length()) {
return s2.length()-j;
}
else if(j==s2.length()) {
return s1.length()-i;
}

if(s1.charAt(i)==s2.charAt(j)) {
if(dp[i][j]==-1) {
dp[i][j] = helper_dp(s1,s2,i+1,j+1,dp);
}
return dp[i][j];
}
else {
if(dp[i+1][j]==-1) {
dp[i+1][j] = helper_dp(s1,s2,i+1,j,dp);
}
if(dp[i][j+1]==-1) {
dp[i][j+1] = helper_dp(s1,s2,i,j+1,dp);
}
return 1+Math.min(dp[i+1][j],dp[i][j+1]);
}

}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.