Share my straight forward JAVA DP solution


  • 0
    C

    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;
        }
    }
    

Log in to reply
 

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