說(shuō)白了就是一個(gè)密碼盤(pán)鄙早，旋轉(zhuǎn)得到相應(yīng)密碼，求拼得某詞匯的最小路徑螟蝙。唯一需要注意是每轉(zhuǎn)到12點(diǎn)方向，摁中間button也算一步民傻，其實(shí)就是最后加上keyword長(zhǎng)度就好胰默。（假設(shè)：1. 密碼一定能被拼出 2. 順時(shí)針逆時(shí)針都可以轉(zhuǎn)）

巨大的密碼盤(pán)圖

Example:

Input: ring = "godding", key = "gd"
Output: 4
Explanation:
 For the first key character 'g', since it is already in place, we just need 1 step to spell this character. 
 For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to 
make it become "ddinggo".
 Also, we need 1 more step for spelling.
 So the final output is 4.

Note:
Length of both ring and key will be in range 1 to 100.
There are only lowercase letters in both strings and might be some duplcate characters in both strings.
It's guaranteed that string key could always be spelled by rotating the string ring.

思路

動(dòng)態(tài)規(guī)劃，因?yàn)闇惖米疃搪窂叫枰坝憙r(jià)還價(jià)”漓踢，也就是能化成子問(wèn)題和遞推狀態(tài)方程牵署。

步驟

1. 畫(huà)DP的表格，用一個(gè)例子推倒一遍過(guò)程喧半，發(fā)現(xiàn)程序邏輯規(guī)律碟刺。
2. 寫(xiě)dp表格格式，分析是2D還是1D薯酝，用Boolean[][]還是int[][], 學(xué)會(huì)用int替代String半沽。
3. 循環(huán)，可以從后往前循環(huán)比較直觀對(duì)應(yīng)子問(wèn)題吴菠。
4. 記得初始化dp[i][j]者填，Integer.MAX_VALUE or 1 or true.
5. 注意比較條件，遞推方程怎么依附于子問(wèn)題做葵。
6. 可以打印出dp debug占哟。
7. 注意返回值是否符合要求。
8. 注意邊界情況，array==null or length==0

注意的點(diǎn)

1. 不論從后往前還是從前往后榨乎，都要預(yù)留出一行

代碼

i從m-1到0的方法

class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        int[][] dp = new int[m+1][n];
        
        for(int i = m-1;i>=0;i--){
            for(int j = 0;j<n;j++){
                dp[i][j]=Integer.MAX_VALUE;
                for(int k=0;k<n;k++){
                    if(ring.charAt(k)==key.charAt(i)){
                        int diff = Math.abs(j-k);
                        int step = Math.min(diff,n-diff);
                        dp[i][j] = Math.min(dp[i][j],step+dp[i+1][k]);
                    }
                }
            }
        }
        
        for(int i=0;i<m+1;i++){
            for(int j=0;j<n;j++){
                System.out.print(dp[i][j]+", ");
            }
            System.out.println();
        }
        /*
        2, 3, 4, 5, 5, 4, 3, 
        2, 1, 0, 0, 1, 2, 3, 
        0, 0, 0, 0, 0, 0, 0, 
        */
        
        // Add m at last, because spelling of each char takes 1 step.
        return dp[0][0]+m;
    }
}

i從1到m的方法

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