android做网站,做网站用的主机多少合适,南通网站开发招聘,网站建设 广告思路#xff1a;动态规划前缀和
这道题还是很难的#xff0c;因为你如果需要推出状态方程是很难想的。
在题中我们其实可以发现#xff0c;这里在访问nextVisit数组的过程中#xff0c;其实就是对于当前访问的房子之前的房子进行了回访。
怎么说呢#xff1f;比如你现在…思路动态规划前缀和
这道题还是很难的因为你如果需要推出状态方程是很难想的。
在题中我们其实可以发现这里在访问nextVisit数组的过程中其实就是对于当前访问的房子之前的房子进行了回访。
怎么说呢比如你现在在第i个房间里你为什么会在第i个房间呢是因为前面的房间你都已经访问了偶数次才会到达这里的吧是的我们发现在规则上说其实就是在访问偶数次之后我们才会向右边的房间去在这之前也就是这间房子左边我们都已经访问偶数次了。
那我们不妨可以看看从某个房间到达奇数次--这个房间到达偶数次这个状态是怎么样的。我们发现不论你选取哪一个房子都是要经历这个过程的所以我们可以把状态方程f的含义定为
访问第i间房子的奇数次到访问第i间房子的偶数次所需要的天数。这就是f[i]的含义。
那么我们可以推知从第j间房子访问到第i间房子的总天数就是f[i]f[j]f[j1]...f[i-1]2.
为什么需要2呢因为你在第一次访问第i间房子之后你需要回访然后再回来的时候才会访问偶数次也就是访问了2次也就是两天其他的那些和其实就是你回访其他房间所用的时间。
好了如果我们真需要处理这些和的话势必会让时间复杂度变成n**2。怎么才能进行优化呢
说到求和我们会想到一个知识点那就是前缀和前缀和会用On的时间来进行操作这样的话就好说了我们就用前缀和进行优化。
设s为前缀和数组那么s[0]0至于为什么需要这样参考一下灵神在这道题里面的题解的解释303. 区域和检索 - 数组不可变 - 力扣LeetCode
那么就这样推下去的话s[1]f[0],s[2]f[1]f[0]......s[i1]f[i]s[i]
而我们上面写的f[i]也就可以化简为f[i]s[i]-s[j]2我们把这两个式子结合一下
就变成了s[i1]s[i]*2-s[j]2。这样就算是完成了
class Solution {
public:int firstDayBeenInAllRooms(vectorint nextVisit) {int nnextVisit.size();const int mod1e97;vectorlongs(n);for(int i0;in-1;i){int jnextVisit[i];s[i1](s[i]*2-s[j]2mod)%mod;}return s[n-1];}
};
