遇到一个寻找等比数列的问题，求解答。
Alice和Bob都是数学高手，有一天Alice给了Bob一个长度为n的数组a，要求 Bob 在数组中找出 3 个数，要求三个数能够组成一个公比为k的等比数列，且不改变三个数在数组 a 中的位置关系。为了降低难度，Alice只要求Bob回答数组a中有多少个这样的等比数列。输入一个整数n表示数组长度、公比k(1<=n,k<=2*10^5) 和包含n个数的数组a(-10^9<=ai<=10^9)输出一个数字，表示数组a中包含Alice 要求的等比数列的数量。
写回答
-
本题充分利用下面两个隐藏规律，就可以使用动态规划： 1. “长度为 3 的等比数列”，满足了动态规划的最优子结构性质数列中每个数字只有 4 种可能的状态。其中带 * 号的状态可以同时存在，且靠后的状态可以由前面的状态转换而来： ● 同时属于一个或多个等比数列的第 1 项 ● 同时属于一个或多个等比数列的第 2 项 ● 同时属于一个或多个等比数列的第 3 项 ● 无法与前后数字组成任何等比数列 2. “不允许调换顺序”，满足动态规划的子问题不重叠性和无后效性性质表示数字处于上面哪种状态，完全由这个数字及其之前的数字决定，它的状态与它后面数字的情形无关。这就意味着，一次遍历，同时用 map 将每个遍历的数字归属到前面 4 种状态中的1个或多个里。遍历结束，输出第 3 种状态“同时属于一个或多个等比数列的第 3项”中含有的数字数就完成了动态规划的过程。 因此输入：5 2 [1,1,2,2,4] 输出：4
2021-12-23 18:32:43赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
