题解 | #牛牛摇骰子#

题意整理

给定一个一维数轴，起点在原点，每次可以向左或者向右移动0或3或7或11个单位。
为了移动到目标点target，计算最少的移动次数。
输入对应的target坐标集合，返回对应的移动次数集合。

方法一（动态规划）

1.解题思路

首先计算移动到 $0-11$ 范围内的目标点对应的最少移动次数。
初始化dp数组。
由于 $0-11$ 范围内的所有情况都统计了，目标点在大于11的范围时，只需从之前的点后移3位、7位或者11位，不用再左移了（所有的点都能通过右移到达，左移会增加移动次数）。所以状态转移方程是： $dp[i]=Math.min(dp[i-3],Math.min(dp[i-7],dp[i-11]))+1$ 。
根据状态转移方程，计算所有可能的情况，然后将dp数组对应的移动次数赋值到结果数组。

计算 $0-11$ 范围内目标点的过程：

0, // 目标点为0，无需移动
3, // 目标点为1，1=7-3-3
4, // 目标点为2，2=7+3+3-11
1, // 目标点为3，3=3
2, // 目标点为4，4=7-3
3, // 目标点为5，5=11-3-3
2, // 目标点为6，6=3+3
1, // 目标点为7，7=7
2, // 目标点为8，8=11-3
3, // 目标点为9，9=3+3+3
2, // 目标点为10，10=7+3
1, // 目标点为11，11=11

测试数据较大时，会超过内存限制。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型一维数组 要查询坐标的数组
     * @return int整型一维数组
     */

    public int[] MinimumTimes (int[] arr) {
        int n=arr.length;
        //初始化结果数组以及终点在0-11某一处时对应的移动次数
        int[] res=new int[n];
        int[] init=new int[]{0,3,4,1,2,3,2,1,2,3,2,1};
        int max=-1;
        //求最大值
        for(int i=0;i<n;i++){
            max=Math.max(max,arr[i]);
        }
        //初始化dp数组
        int[] dp=new int[max+1];
        for(int i=0;i<=max;i++){
            if(i<12){
                dp[i]=init[i];
            }
            //状态转移
            else{
                dp[i]=Math.min(dp[i-3],Math.min(dp[i-7],dp[i-11]))+1;
            }
        }

        //赋值给结果数组
        for(int i=0;i<n;i++){
            res[i]=dp[arr[i]];
        }
        return res;
    }


}

3.复杂度分析

时间复杂度：所有的循环均为线性遍历，假设arr数组最大值为max，所以最终的时间复杂度为 $O(n+max)$ 。
空间复杂度：需要额外大小为max的dp数组，所以空间复杂度为 $O(max)$ 。

方法二（数学）

1.解题思路

将方法一中dp数组的前78个数，打印出来可得：

0--3--4--1--2--3--2--1--2--3--2--1
   4--3--2--3--4--3--2--3--4--3--2
   5--4--3--4--5--4--3--4--5--4--3
   6--5--4--5--6--5--4--5--6--5--4
   7--6--5--6--7--6--5--6--7--6--5
   8--7--6--7--8--7--6--7--8--7--6
   9--8--7--8--9--8--7--8--9--8--7

可以发现除了第0项以及第2项，之后的每一行都由前一行对应项加一所得。

初始化结果数组以及init数组。
遍历arr数组，如果是第二项，直接返回4。
每隔11个数，由第一行对应的数加上行号即可得到当前项的值。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型一维数组 要查询坐标的数组
     * @return int整型一维数组
     */

    public int[] MinimumTimes (int[] arr) {
        int n=arr.length;
        //初始化结果数组以及终点在0-11某一处时对应的移动次数
        int[] res=new int[n];
        int[] init=new int[]{0,3,2,1,2,3,2,1,2,3,2,1};

        for(int i=0;i<n;i++){
            //特殊点
            if(arr[i]==2){
                res[i]=4;
                continue;
            }
            //每隔11个数，由第一行对应的数加上行号
            res[i]=arr[i]/11+init[arr[i]%11];
        }

        return res;
    }

}

3.复杂度分析

时间复杂度：需要遍历arr数组一次，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。