# Share my straight forward JAVA DP solution

• DP is about memorization, all I did here is to remember the cost to get each key[i], and use the minimum of dp[i-1][0...n-1] to get dp[i][j]. The idea is similar to https://leetcode.com/problems/triangle/#/description

``````public class Solution {
public int findRotateSteps(String ring, String key) {
char [] r = ring.toCharArray();
char [] ky = key.toCharArray();
int n = r.length;
int m = ky.length;
int dp[][] = new int[m][n];
for(int i = 0 ; i < m; i++){
for(int j = 0 ; j < n; j++){
dp[i][j] = Integer.MAX_VALUE;
if(r[j] == ky[i]){
if(i == 0){
int step = Math.min(j, n - j);
dp[i][j] = step + 1;
}else{
for(int k = 0; k < n; k++){
if(dp[i-1][k] != Integer.MAX_VALUE){
int diff = Math.abs(k-j);
int step = Math.min(diff, n - diff);
dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + step + 1);
}
}
}
}
}
}
int min = Integer.MAX_VALUE;
for(int i = 0 ; i< n; i++){
min = Math.min(dp[m-1][i], min);
}
return min;
}
}
``````

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