算法50：动态规划专练(力扣514题：自由之路-----4种写法)

题目: 力扣514 ：自由之路 . - 力扣（LeetCode）

题目的详细描述，直接打开力扣看就是了，下面说一下我对题目的理解:

事例1：

输入: ring = "godding", key = "gd"
输出: 4.

1. ring的第一个字符默认是指向12点方向的，这一点很重要

2. key的第一个字符为g，而ring中首字符和末尾字符都为g。因此，必然存在选择首字符的g还是末尾字符g的问题。

3. 即使ring中第一个字符为g，也还存在存在顺时针旋转和逆时针旋转的问题。(当然，当前案例比较极端，如果第一个字符不为g，理解起来更合适)

4. 这一题要求的是旋转的最小步数。因此，最终的值必然是获取最小值的。

5. 那么整体串起来分析：

ring = "godding", key = "gd"

字符	g	o	d	d	i	n	g
下标	0	1	2	3	4	5	6

a1. 如果ring的第一个g旋转，顺时针步数为0；逆时针步数为7；算上最终确认的1步，因此就是在 1 和 8中选取最小值，选取1

a2. 接着a1继续分析，既然key的第一个字符已经确定了。那么key的第二个字符d又该选择了。我们到底是用下标为2的d呢，还是使用下标为3的d呢？

选择1：下标为2的d，从a1的g顺时针旋转只需要2步，逆时针旋转需要5步，。算上确认的1步，就是在3和6中选取最小值，选取3

选择2：下标为3的d, 从a1的g顺时针旋转只需要3步，逆时针旋转需要4步。算上确认的1步，就是在4和5中选取最小值. 选取 4

如果g使用的是ring中第一个字符，针对以上2种选择，最好的选择就是使用下标为2的d，顺时针旋转2步，即3步。那么，总的代价就是 1 + 3 = 4。

开头，我们就说过，ring中有开头和结尾都存在g，因此存在选择的问题。

b1. 如果我们使用ring中下标为6的g最为key的开头。顺时针旋转需要1步，逆时针旋转需要6步，算上最终确认的1步，就是2步和7步。选取最小值2.

b2. 接着b1继续分析，既然key的第一个字符已经确定了。那么key的第二个字符d又该选择了。我们到底是用下标为2的d呢，还是使用下标为3的d呢？

选择1：下标为2的d，从b1的g顺时针旋转只需要4步，逆时针旋转需要3步，。算上确认的1步，就是在5和4中选取最小值，选取4

选择2：下标为3的d, 从b1的g顺时针旋转只需要3步，逆时针旋转需要4步。算上确认的1步，就是在4和5中选取最小值. 选取4

如果g使用的是ring中最后一个字符，针对以上2种选择，最好都为4。那么，总的代价就是 2 + 4 = 6。

最终，如果以ring中第一个g作为旋转选择，最小的步数为4; 以ring中最后一个g作为旋转选择，那么最小步数为6；因此，当前案例最小步数为 Math.min(4, 6).

递归代码：

package 刷题.第三天;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 力扣514： 自由之路
 * https://leetcode.cn/problems/freedom-trail/
 */
public class C2_FreeDomTtail_leet514_递归 {

    //递归版本
    public int findRotateSteps(String ring, String key) {

        if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
            return 0;
        }

        char[] source = ring.toCharArray();
        char[] target = key.toCharArray();

        //记录下每个字符的位置，有可能存在重复值的情况
        HashMap<Character, List> map = new HashMap<Character, List>();
        for (int i = 0; i < ring.length(); i++) {
            if (map.containsKey(source[i])) {
                //放入下标的位置
                map.get(source[i]).add(i);
            }
            else {
                List list = new ArrayList();
                list.add(i);
                map.put(source[i], list);
            }
        }

        return process(map, source, 0, target, 0);
    }


    public int process (Map<Character, List> map,
                        char[] source, int sourceStartIndex,
                        char[] target, int targetIndex) {
        if (targetIndex == target.length) {
            return 0;
        }

        List<Integer> ops = map.get(target[targetIndex]);
        int minStep = Integer.MAX_VALUE;
        for (int i = 0; i < ops.size(); i++) {
            //从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步
            int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;

            //深度优先遍历； 此时source的的开始位置为 ops.get(i)
            minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1));
        }

        return minStep;
    }

    //获取从最小长度
    public int getMinSteps(int start, int end, int size)
    {
        //如果start < end, 则是顺时针; 反之， 逆时针
        int step1 = Math.abs(start - end);

        //如果step1是顺时针，那么step则是逆时针; 反之，顺时针
        int step2 = size - step1;

        return Math.min(step1, step2);
    }

    public static void main(String[] args) {
        C2_FreeDomTtail_leet514_递归 ss = new C2_FreeDomTtail_leet514_递归();
        String source = "godding";
        String target = "gd";

        System.out.println(ss.findRotateSteps(source, target));
    }
}

测试结果：

超时是好事情，说明整体逻辑大概率是没有问题的。超时，说明递归计算的次数有问题。上方的分析过程中，a2和b2 都是针对d进行逻辑判断的，明显存在重复的过程。那么，就需要在递归的基础之上添加缓存了，俗称记忆化搜索。

我之前在说动态规划的时候就说过，如果表结构依赖不严格，或者说即使依赖严格表结构，但是没有优化的空间。递归 + 缓存 == 动态规划。

递归+缓存版本：

package 刷题.第三天;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 力扣514： 自由之路
 * https://leetcode.cn/problems/freedom-trail/
 */
public class C2_FreeDomTtail_leet514_递归_缓存 {

    //递归 + 缓存
    public int findRotateSteps(String ring, String key) {

        if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
            return 0;
        }

        char[] source = ring.toCharArray();
        char[] target = key.toCharArray();

        //记录下每个字符的位置，有可能存在重复值的情况
        HashMap<Character, List> map = new HashMap<Character, List>();
        for (int i = 0; i < ring.length(); i++) {
            if (map.containsKey(source[i])) {
                //放入下标的位置
                map.get(source[i]).add(i);
            }
            else {
                List list = new ArrayList();
                list.add(i);
                map.put(source[i], list);
            }
        }

        int[][] dp = new int[source.length][target.length];
        for (int i = 0; i < source.length; i++) {
            for (int j = 0; j < target.length; j++) {
                //代表没算过
                dp[i][j] = -1;
            }
        }

        return process(map, source, 0, target, 0, dp);
    }


    public int process (Map<Character, List> map,
                        char[] source, int sourceStartIndex,
                        char[] target, int targetIndex,
                        int[][] dp) {

        if (targetIndex == target.length) {
            return 0;
        }

        //缓存
        if (dp[sourceStartIndex][targetIndex] != -1) {
            return dp[sourceStartIndex][targetIndex];
        }

        List<Integer> ops = map.get(target[targetIndex]);
        int minStep = Integer.MAX_VALUE;
        for (int i = 0; i < ops.size(); i++) {
            //从sourceStartIndex 到 ops.get(i) 最下步数; +1是确认按钮耗费的1步
            int step = getMinSteps(sourceStartIndex, ops.get(i), source.length) + 1;

            //深度优先遍历； 此时source的的开始位置为 ops.get(i)
            minStep = Math.min(minStep, step + process(map, source, ops.get(i), target, targetIndex + 1, dp));

            dp[sourceStartIndex][targetIndex] = minStep;
        }

        return minStep;
    }

    //获取从最小长度
    public int getMinSteps(int start, int end, int size)
    {
        //如果start < end, 则是顺时针; 反之， 逆时针
        int step1 = Math.abs(start - end);

        //如果step1是顺时针，那么step则是逆时针; 反之，顺时针
        int step2 = size - step1;

        return Math.min(step1, step2);
    }

    public static void main(String[] args) {
        C2_FreeDomTtail_leet514_递归_缓存 ss = new C2_FreeDomTtail_leet514_递归_缓存();
        String source = "godding";
        String target = "gd";

        System.out.println(ss.findRotateSteps(source, target));
    }
}

测试结果：

84%的胜率，8毫秒，已经相当优秀了。其实，这就是最优解

第三版本：纯动态规划

动态规划，那就需要分析递归的逻辑了。下面以ring作为行，以key作为列

第一步：

	0 (g)	1 (d)
0 (g）	下标0的g: 顺时针：1步逆时针：8步选取1步
1 (o)
2 (d)
3 (d)
4 (i)
5 (n)
6 (g)	下标6的g : 顺时针：2步逆时针：7步选取2步

第二步：

	0 (g)	1 (d)
0 (g）	下标0的g: 1步
1 (o)
2 (d)		下标为2的d：从下标为0的g过来，顺时针2步，逆时针5步，算上确认的1步，就是3步和6步，选取小值，即3步从下标为6的g过来，顺时针3步，逆时针4步，算上确认的1步，就是4步和5步，选取小值，即4步最终值就是: 1+3 和 2 +4选取小的。即4步 1是下标为0的g耗费的1步 2是下标为6的g耗费的2步
3 (d)		下标为3的d：从下标为0的g过来，顺时针3步，逆时针4步，算上确认的1步，就是4步和5步，选取小值，即4步从下标为6的g过来，顺时针4步，逆时针3步，算上确认的1步，就是5步和4步，选取小值，即4步最终值就是: 1+4 和 2 +4选取小的。即5步 1是下标为0的g耗费的1步 2是下标为6的g耗费的2步
4 (i)
5 (n)
6 (g)	下标6的g : 2步

因此，最终最小的步数就是当key遍历完最后一个字符得到，即 1 + 3 = 4步；

纯动态规划

package 刷题.第三天;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 力扣514： 自由之路
 * https://leetcode.cn/problems/freedom-trail/
 */
public class C2_FreeDomTtail_leet514_动态规划 {

    //纯动态规划
    public int findRotateSteps(String ring, String key) {

        if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
            return 0;
        }

        char[] source = ring.toCharArray();
        char[] target = key.toCharArray();

        //记录下每个字符的位置，有可能存在重复值的情况
        HashMap<Character, List> map = new HashMap<Character, List>();
        for (int i = 0; i < ring.length(); i++) {
            if (map.containsKey(source[i])) {
                //放入下标的位置
                map.get(source[i]).add(i);
            }
            else {
                List list = new ArrayList();
                list.add(i);
                map.put(source[i], list);
            }
        }

        int[][] dp = new int[source.length][target.length + 1];
        //最终返回的最小值
        int finalMinStep = Integer.MAX_VALUE;
        //第一列
        List<Integer> ops = map.get(target[0]);
        for (int index : ops) {
            dp[index][0] = getMinSteps(0, index, source.length) + 1;
            //如果要拼接的key只有一个字符，直接获取最小值即可
            finalMinStep = Math.min(finalMinStep,  dp[index][0]);
        }

        //如果要拼接的字符长度超过1，那么finalMinStep的值需要
        //等到 target的最后一列才能确定
        if (target.length > 1) {
            finalMinStep = Integer.MAX_VALUE;
        }
        //列遍历，从第二列开始往后遍历
        for (int i = 1; i < target.length ; i++)
        {
            //当前列对应的行信息
            List<Integer> ops2 = map.get(target[i]);
            //当前列前一列对应的行信息
            List<Integer> ops3 = map.get(target[i-1]);

            for (int j : ops2)  //结束
            {
                //j行i列的默认最小值
                int minStep = Integer.MAX_VALUE;
                for(int m : ops3) //开始
                {
                    //从m行到j行的步数
                    int curStep = getMinSteps(m, j, source.length) + 1;
                    //dp[m][i-1] : 从0到m累计步数
                    //dp[j][i-1] + curStep ： 代表从0行到j行累计步数
                    int steps = dp[m][i-1] + curStep;
                    //更新j行i列的最小值
                    minStep = Math.min(minStep, steps);
                    dp[j][i] = minStep;
                }

                //要拼接字符串的最后一个字符，也就是说可以
                //已经全部拼接完了
                if (i == target.length - 1) {
                    finalMinStep = Math.min(finalMinStep, dp[j][i]);
                }
            }
        }

        return finalMinStep;
    }


    //获取从最小长度
    public int getMinSteps(int start, int end, int size)
    {
        //如果start < end, 则是顺时针; 反之， 逆时针
        int step1 = Math.abs(start - end);

        //如果step1是顺时针，那么step则是逆时针; 反之，顺时针
        int step2 = size - step1;

        return Math.min(step1, step2);
    }

    public static void main(String[] args) {
        C2_FreeDomTtail_leet514_动态规划 ss = new C2_FreeDomTtail_leet514_动态规划();
        /*String source = "godding";
        String target = "gd";*/

        String source = "eh";
        String target = "h";

        System.out.println(ss.findRotateSteps(source, target));
    }
}

测试结果：