关于leetcode:听说逆向思维能够降低时间复杂度

以终为始在日常生活中指的是 先确定指标，再做好打算。之前读管理学的书的时候，学到了这个概念。

而在算法中，以终为始指的是 从后果反向推，直到问题的初始状态。

那么什么时候适宜反向思考呢？一个很简略的准则就是：

1. 正向思考的状况比拟多
2. 代码比拟难写或者算法简单度过高

这个时候咱们能够思考反向操作。

我的习惯是如果间接求解很难，我会优先思考应用能力检测二分，如果不行我则会思考反向思考。

对于能力检测二分，能够在我的公众号中找到，大家能够在《力扣加加》回复二分获取。

明天西法通过三道题来给大家聊聊到底怎么在写算法题的时候使用 以终为始 思维。

机器人跳跃问题

这道题来自于牛客网。地址：nowcoder.com/question/next?pid=16516564&qid=362295&tid=36905981

题目形容

工夫限度：C/C++ 1 秒，其余语言 2 秒

空间限度：C/C++ 32M，其余语言 64M

机器人正在玩一个古老的基于 DOS 的游戏。游戏中有 N + 1 座修建——从 0 到 N 编号，从左到右排列。编号为 0 的修建高度为 0 个单位，编号为 i 的修建的高度为 H(i)个单位。起初，机器人在编号为 0 的修建处。每一步，它跳到下一个（左边）修建。假如机器人在第 k 个修建，且它当初的能量值是 E, 下一步它将跳到第个 k + 1 修建。它将会失去或者失去反比于与 H(k+1)与 E 之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将失去 E - H(k+1) 的能量值。游戏指标是达到第个 N 修建，在这个过程中，能量值不能为正数个单位。当初的问题是机器人以多少能量值开始游戏，才能够保障胜利实现游戏？输出形容:
第一行输出，示意一共有 N 组数据.

第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度

输入形容:
输入一个独自的数示意实现游戏所需的起码单位的初始能量

输出例子 1:
5
3 4 3 2 4

输入例子 1:
4

输出例子 2:
3
4 4 4

输入例子 2:
4

输出例子 3:
3
1 6 4

输入例子 3:
3

思路

题目要求初始状况下至多须要多少能量。正向求解会比拟艰难，因而我的想法是：

1. 能力检测二分。比方能量 x 是否能够，如果 x 能够，那么大于 x 的能量都能够。依此咱们不难写出代码。
2. 反向思考。尽管咱们不晓得最开始的能量是多少，然而咱们晓得最初的能量是 0 才最优，基于此咱们也能够写出代码。

这里咱们应用第二种办法。

具体来说：咱们从后往前思考。达到最初一级的能量起码是 0。而因为:

next = pre + (pre - H[i])

因而：

pre = (next + H[i]) / 2

因为除以 2 可能会呈现小数的状况，因而须要 ceil。

你能够：

pre = math.ceil((next + H[i]) / 2)

也能够：

pre = (next + H[i] + 1) // 2

// 是地板除，即向下取整

代码（Python）

n = input()
H = input().split(" ")
ans = 0
for i in range(len(H) - 1, -1, -1):
    ans = (ans + int(H[i]) + 1) // 2
print(ans)

复杂度剖析

• 工夫复杂度：$O(n)$
• 空间复杂度：$O(1)$

这个题目的要害一句话总结就是：咱们须要确定起码须要多少初始能量，因而咱们是不确定最后的能量的，咱们能够确定的是达到最初一个修建能量是 0 才最优。

2139. 失去目标值的起码口头次数

第二道题是 2022.01 月份的一场周赛的第二题，题目还是比拟新的。

题目地址

https://leetcode-cn.com/probl…

题目形容

你正在玩一个整数游戏。从整数 1 开始，冀望失去整数 target。在一次口头中，你能够做下述两种操作之一：递增，将以后整数的值加 1（即，x = x + 1）。加倍，使以后整数的值翻倍（即，x = 2 * x）。在整个游戏过程中，你能够应用 递增 操作 任意 次数。然而只能应用 加倍 操作 至少 maxDoubles 次。给你两个整数 target 和 maxDoubles，返回从 1 开始失去 target 须要的起码口头次数。示例 1：输出：target = 5, maxDoubles = 0
输入：4
解释：始终递增 1 直到失去 target。示例 2：输出：target = 19, maxDoubles = 2
输入：7
解释：最后，x = 1。递增 3 次，x = 4。加倍 1 次，x = 8。递增 1 次，x = 9。加倍 1 次，x = 18。递增 1 次，x = 19。示例 3：输出：target = 10, maxDoubles = 4
输入：4
解释：最后，x = 1。递增 1 次，x = 2。加倍 1 次，x = 4。递增 1 次，x = 5。加倍 1 次，x = 10。提醒：1 <= target <= 109
0 <= maxDoubles <= 100

思路

因为刚开始数字为 1，最终状态为 target。因而正向思考和反向思考都是 ok 的。

而如果正向模仿的话，尽管很容易实现，然而工夫复杂度太高。

这是因为从 1 开始咱们有两个抉择（如果依然能够加倍），接下来依然有两个抉择（如果依然能够加倍）。。。

因而工夫复杂度大抵为 $O(target * maxDoubles)$。代入题目给的数据范畴显然是无奈通过的。

而正向思考比拟艰难，咱们无妨从反向进行思考。

从 target 开始，如果 target 是奇数，显然咱们只能通过 + 1 而来，即便咱们依然能够加倍。这样工夫复杂度就升高了。不过这还不够，进而咱们发现如果 target 为偶数咱们应该抉择加倍到 target（如果依然能够加倍），而不是 + 1 到 target。这是因为

1. 咱们是反向思考的，如果你当初不抉择加倍而是前面再抉择加倍那么加倍带来的收益会更低
2. 加倍的收益肯定大于 + 1，换句话说加倍能够更快达到 target。

基于此，不难写出如下代码。

代码

• 语言反对：Python3

Python3 Code:

class Solution:
    def minMoves(self, target: int, maxDoubles: int) -> int:
        ans = 0
        while maxDoubles and target != 1:
            ans += 1
            if target % 2 == 1:
                target -= 1
            else:
                maxDoubles -= 1
                target //= 2
        ans += (target - 1)
        return ans

复杂度剖析

如果 maxDoubles 无限大，那么工夫大略是 $log target$。而如果 target 无限大，那么工夫大略是 maxDoubles。因而工夫复杂度为 $O(min(maxDouble, log target))$

• 工夫复杂度：$O(min(maxDouble, log target))$
• 空间复杂度：$O(1)$

LCP 20. 疾速公交

最初一道题是力扣杯的一道题，难度为 hard，咱们来看下。

题目地址(20. 疾速公交)

https://leetcode-cn.com/probl…

题目形容

小扣打算去秋日市集，因为游客较多，小扣的挪动速度受到了人流影响：小扣从 x 号站点挪动至 x + 1 号站点须要破费的工夫为 inc；小扣从 x 号站点挪动至 x - 1 号站点须要破费的工夫为 dec。现有 m 辆公交车，编号为 0 到 m-1。小扣也能够通过搭乘编号为 i 的公交车，从 x 号站点挪动至 jump[i]*x 号站点，耗时仅为 cost[i]。小扣能够搭乘任意编号的公交车且搭乘公交次数不限。假设小扣起始站点记作 0，秋日市集站点记作 target，请返回小扣到达秋日市集起码须要破费多少工夫。因为数字较大，最终答案须要对 1000000007 (1e9 + 7) 取模。留神：小扣可在挪动过程中达到编号大于 target 的站点。示例 1：输出：target = 31, inc = 5, dec = 3, jump = [6], cost = [10]

输入：33

解释：小扣步行至 1 号站点，破费工夫为 5；小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台，破费工夫为 10；小扣从 6 号站台步行至 5 号站台，破费工夫为 3；小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台，破费工夫为 10；小扣从 30 号站台步行至 31 号站台，破费工夫为 5；最终小扣破费总工夫为 33。示例 2：输出：target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]

输入：26

解释：小扣步行至 1 号站点，破费工夫为 4；小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，破费工夫为 4；小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，破费工夫为 3；小扣从 33 号站台步行至 34 站台，破费工夫为 4；小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，破费工夫为 4；小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，破费工夫为 7；最终小扣破费总工夫为 26。提醒：1 <= target <= 10^9
1 <= jump.length, cost.length <= 10
2 <= jump[i] <= 10^6
1 <= inc, dec, cost[i] <= 10^6

思路

因为终点是 0，起点是 target。和下面一样，正向思考和反向思考难度差不多。

那么咱们能够正向思考么? 和下面一样正向思考状况太多，简单度过高。

那么如何反向思考呢？反向思考如何优化复杂度的呢？

因为题目能够在挪动过程中达到编号大于 target 的站点，因而正向思考过程中坐标大于 target 的很多点咱们都须要思考。

而如果反向思考，咱们是 不能在挪动过程中达到编号大于 0 的站点的 ，因而状况就大大减少了。而达编号大于 target 的站点只须要思考 向右挪动后再乘坐公交返回 target 的状况即可（也就是说咱们是做了公交而后往回走的状况）

对于每一个地位 pos，咱们都思考：

1. 全副走路
2. 间接乘公交
3. 走几步再乘公交

在这三种状况取最小值即可。

问题的要害是状况 3，咱们如何计算是走几步再乘公交呢？如果反向思考，咱们能够很简略地通过 pos % jump[i] 算进去，而开始乘公交的点则是 pos // jump。

代码

• 语言反对：Python3

Python3 Code:

class Solution:
    def busRapidTransit(self, target: int, inc: int, dec: int, jumps: List[int], cost: List[int]) -> int:
        @lru_cache(None)
        def dfs(pos):
            if pos == 0: return 0
            if pos == 1: return inc
            # 最坏的状况是全副走路，不乘公交，这种状况工夫为 pos * inc
            ans = pos * inc
            for i, jump in enumerate(jumps):
                pre_pos, left = pos // jump, pos % jump
                if left == 0: ans = min(ans, cost[i] + dfs(pre_pos))
                else: ans = min(ans, cost[i] + dfs(pre_pos) + inc * left, cost[i] + dfs(pre_pos + 1) + dec * (jump - left))
            return ans
        return dfs(target) % 1000000007

复杂度剖析

令 T 为 jump 数组的长度。

• 工夫复杂度：$O(target * T)$
• 空间复杂度：$O(target)$

总结

反向思考往往能够达到降维打击的成果。有时候能够使得求解思路更简略，代码更好写。有时候能够使得状况更少，复杂度升高。

回顾一下什么时候应用反向思考呢？一个很简略的准则就是：

1. 正向思考的状况比拟多
2. 代码比拟难写或者算法简单度过高

我给大家举了三个例子来阐明如何使用反向思考技巧。其中

• 第一题正向思考只能应用逐个枚举的形式，当然咱们能够应用二分升高复杂度，然而复杂度依然不迭反向思考。
• 第二题反向思考状况大大减少，复杂度指数级升高，真的是降维打击了。
• 第三题利用无奈超过 0 的地位这点，反向思考升高复杂度。

这些题还是冰山一角，理论做题过程中你会发现 反向思考很常见，只是支流的算法划分没有对应的专题罢了 。我甚至还有想法将其退出91 天学算法中，就像前期加 枚举章节一样，我认为反向思考也是一个根底的算法思考，请诸君务必把握！