牛牛摇骰子题解

20分解法：

由于最多的查询次数只有5次，我们可以每次根据p的值进行查询，查询方法可以用bfs，每次查询复杂度o（P）时间复杂度o（TP）。空间复杂度为o（TP）。这里如果用bfs时有一个需要注意的地方，就是我们要到达的bfs的可行点的范围不能只设为0-p。打个比方，我们要到点8，最小步数是2：一.向左走一步3 二.向右走一步11，但不论我们按什么顺序执行这两步都会走出0-8这个区间，所以要注意给可行区间至少在一个方向留出多余的空间来判定。

50分解法：

我们发现可以先将p范围内所有的的值对应的答案全部查询出来,将答案打表存在一个数组里，这样对于每次查询我们可以o（1）的获得答案，时间复杂度o（P），空间复杂度为o（P）。

100分解法

此时p的范围最大是1e9，显然不论是dp还是bfs都不能在合理的时间内查询出答案。这是我们采用贪心的思想，对于每个3、7、11的最小公倍数的块，显然走的越多所需步数更小，也就是当p足够大时其实绝大多数筛子点数的选择都是11，我们只需要留一个比最小公倍数大的块算出这块所需要的步数即可，其他步全部选择11。最小公倍数为3x7x11=231。我们记录一下500以内的每个数需要走几步即可。
对于这一段每个数需要走几步，这里介绍两种做法：

1.dp

我们可以先模拟出走到1-11的最小步数，然后之后的值一定是前面的一个值走1-11步转移而来的，时间复杂度o（最小公倍数），空间复杂度o（最小公倍数），缺点是相较bfs时打表的常数较大，但本题数的范围很小没有卡这个常数，代码如下:

完善核心代码模式代码：

int f[2005];
class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    void init()
    {
        memset(f,0x3f,sizeof(f));
        f[1] = 3;
        f[2] = 4;
        f[3] = 1;
        f[4] = 2;
        f[5] = 3;
        f[6] = 2;
        f[7] = 1;
        f[8] = 2;
        f[9] = 3;
        f[10] = 2;
        f[11] = 1;
  for(int i = 12;i<=2000;i++) {
    for(int j = 1;j<=11;j++) {
      f[i] = min(f[i],f[i-j] + f[j]);
    }
  }
    }
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        init();
        vector<int >g;
        for(int i=0;i<arr.size();i++)
        {
            int p=arr[i];
            if(p<=1000)
            {
                g.push_back(f[p]);
            }
            else
            {
                int ans = (p - 1000)/11;
                p -= (p-1000)/11*11;
                g.push_back(ans + f[p]);
            }
        }
        return g;
    }
};

2.bfs

我们也可以通过bfs的方法得到到达每个点的步数。用bfs的方法优秀的地方在于不用找到前11个点的对应的值，而且虽然时间复杂度和dp方法一样同为o(最小公倍数)，但bfs的常数更小。空间复杂度同为o（最小公倍数）。假如我们把这道题骰子的四个面的值改成53,59,71,73；最小公倍数就是一个2e7左右的数了，此时dp还要乘上一个73的常数，而bfs的常数只有8,所以在这种情况下bfs的优势就更加明显。下面是bfs的代码：

完善核心代码模式代码：

const int maxn=1000;
int jl[maxn+5];
struct poi{
int zhi;
int bu;
};
int dx[]={3,7,11,-3,-7,-11};
bool check(int x)
{
    if(x>=0&&x<=maxn)return 1;
    return 0;
}
class Solution {
public:
    /**
     * 把所有询问的答案按询问顺序放入vector里
     * @param arr int整型vector 要查询坐标的数组
     * @return int整型vector
     */
    void init()
    {
        queue<poi >q;
        q.push((poi){0,0});
        while(!q.empty())
        {
            poi node=q.front();
            q.pop();
            for(int i=0;i<6;i++)
            {
                if(check(node.zhi+dx[i])&&!jl[node.zhi+dx[i]])
                {
                    jl[node.zhi+dx[i]]=node.bu+1;
                    q.push((poi){node.zhi+dx[i],node.bu+1});
                }
            }
        }
    }
    vector<int> MinimumTimes(vector<int>& arr) {
        // write code here
        init();
        vector<int >g;
        for(int i=0;i<arr.size();i++)
        {
            int p=arr[i];
            if(p<=maxn/2)
            {
                g.push_back(jl[p]);
            }
            else
            {
                p-=maxn/2;
                int ans=p/11;
                p%=11;
                p+=maxn/2;
                ans+=jl[p];
                g.push_back(ans);
            }
        }
        return g;
    }
};