Java-LeetCode514. 自由之路-动态规划

• 算法
  • 1.动态规划：dp[i][j]表示匹配到key的第i个字符且ring的第j个字符在12：00位置的最小步数
  • 2.初始状态：dp[0][j] = Math.min(j, n - j) + 1; j ∈ key的第一个字符ring中的位置
  • 3.转移公式：
    • dp[i][j]的计算：只需要计算key中第i个字符出现在ring中的位置的那些j（其他没出现的初始化为MAX_VALUE），如何计算呢？利用key中第i-1个字符出现在ring中的位置的那些k，也即dp[i-1][k]的值，求这些位置到dp[i][j]的最小值，最终就是dp[i][j]
  • 4.最后的答案是dp[m-1]中的最小值，m是key的长度
  • ps：key中字符在ring中的位置可以事先保留在ArrayList中

public int findRotateSteps(String ring, String key) {
    int n = ring.length(), m = key.length();
    List<Integer>[] pos = new List[26];
    for (int i = 0; i < 26; ++i) {
        pos[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < n; ++i) {
        pos[ring.charAt(i) - 'a'].add(i);
    }
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; ++i) {
        Arrays.fill(dp[i], Integer.MAX_VALUE);
    }
    for (int i : pos[key.charAt(0) - 'a']) {
        dp[0][i] = Math.min(i, n - i) + 1;
    }
    for (int i = 1; i < m; ++i) {
        for (int j : pos[key.charAt(i) - 'a']) {
            for (int k : pos[key.charAt(i - 1) - 'a']) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1);
            }
        }
    }
    return Arrays.stream(dp[m - 1]).min().getAsInt();
}