递推算法 | 🌈Yuleo

type

status

date

slug

summary

递推

递推是一种常见的数学方法，也是计算机科学中常用的算法。

递推的基本思想是通过已知的一些值来推导出其他未知值的方法。

递推在计算机科学中广泛应用于算法设计和数据结构中。递推的应用非常广泛，比如在计算斐波那契数列时，可以通过递推来计算第n个斐波那契数。

斐波那契数列的定义是：

F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)。

通过递推可以得到：

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1

F(3) = F(2) + F(1) = 2

F(4) = F(3) + F(2) = 3

F(5) = F(4) + F(3) = 5

F(6) = F(5) + F(4) = 8

可以看到，通过递推可以很方便地计算出斐波那契数列的各项值。递推的关键是通过已知的一些值来计算未知的值。在斐波那契数列中，已知的是F(0)和F(1)，通过这两个值可以递推出其他的值。递推的思想不仅在数学中有应用，在计算机科学中也非常重要。

比如，在动态规划中，递推是一种常见的解决方法，在动态规划中，通常需要通过递推来计算出最优解。比如，在计算机科学中，背包问题是一个经典的动态规划问题。在背包问题中，需要计算出在给定的约束条件下，能装下的最大价值的物品。通过递推可以很方便地计算出最优解。

3777. 砖块

题目要求：给你一个只有’W'和‘B’组成的字符串，每次可以选择一个位置i，并且会自动包含位置i+1，然后把这两个位置的字符改成相反的字符，直到字符串只包含一个字符为止，请你判断有没有解，如果有则输出改变的次数，没有解则输出-1

示例：

i=1 与 i=2 修改：BBBWWWWB

i=3 与 i=4 修改：BBBBBWWB

i=5 与 i=6 修改：BBBBBBBB

所以只需要修改三次即可，输出3.

无法修改这个为同一个字符，无解，输出-1

这道题利用了贪心+递推的思想。

递推：简单说利用前面的递推出后面的。

那么这道题该如何利用递推呢？

可以观察到：第 i 个位置的修改会影响 i+1 位置一起修改，当我们从 i 位置遍历移动到 i+1 的位置的时候，我们的此时的 i 位置已经被上一次操作所影响。所以这就是一个递推的过程。

对于这道题的求解思路：

我们只能对相邻的两个字符进行操作我们可以分别对这个字符串进行‘W‘检查和’B‘检查，如果都不能满足，则输出-1表示无解

观察一些性质：

对第一个字符 s[0] 的操作：

如果检查字符ch==’W’，如果s[0]==’W’，则s[0]一定无须操作；

同理如果检查字符ch==’B’，s[0]==’B’，则s[0]也一定无须操作。

即如果第一个字符和目标字符相同，则我们一定无须替换这个字符，因为操作一次会互换，操作两次就是回到了原来。因此我们只能选择对某一个位置操作一次，操作两次就是又变了回来，因此操作两次无意义。

因此对于所有的字符都是同理，如果某位置字符与目标字符相同，则我们跳过它，直到遇到某位置的字符与目标字符不同，这便是贪心的思想，相同就跳过，不相同就跳过。

则我们改变这个位置和下一个位置的字符为相反的，然后把这个位置记录一下。

最后：如果我们可以对倒数第二个位置进行操作，则说明最后一个位置也会跟着操作，此时分为两种情况：

[n-1]和[n]操作后，[n]位置的字符等于检查字符，则为true，说明有解

[n-1]和[n]操作后，[n]位置的字符不同于检查字符，则为false，说明无解

因为我们无法对最后一个字符进行单独操作，因此根据最后一个字符来判断是否有解

95. 费解的开关

题目要求：5*5的01矩阵，让每次对一位进行操作，会影响到其周围上下左右的四个数字，由0变为1，或者由1变为0，要求能否在6次操作内将全部都变为1

本题也是一道非常经典的递推习题。

并且和上一道题也优有点类似，上一道题是一维的递推，这一道题是二维的递推，其实把这个二维的竖着往下看，其实可以看作一个粗一点的一维的，本质上是一致的。

需要明白，灯的影响顺序总是从上到下影响的，即当前行的当前列影响下一行的当前列。

第一行的某一个位置如果为0，则对应其下一行的这个位置一定需要改变。

同理第二行为0，则可以确定第三行一定需要按

第三行为0，则可以确定第四行也一定需要按

… 因此确定递推关系：根据上一行确定下一行

那么显然第一行需要单独处理，并且我们需要枚举第一行的所有情况，就像《砖块》一样，我们对首元素的枚举是基于‘W’和'B'字符进行的，因此首元素等于W的时候，递推一次；首元素等于B的时候，递推一次，然后对这两种枚举进行归纳。

如果把W和B看作是一种情况，则这道题就是有32种情况，因为每一个01组成的五位二进制数都是不同的，一共有32种，则可以看作第一行枚举32次。

我们把第一行二进制 00000-11111，枚举第一行的32种情况0-31，则我们讨论这31种情况，对于每一种情况我们都进行1->2 2->3 3->4 4->5两行之间的递推，直到遍历完这32种情况，其中每一种都需要统计这种方法的最小次数。

最后一行用于判断有无解，因为最后一行如果全为1，则一定有解；如果存在一个0，则一定无解。由于第四行可以推出第五行，因此最后一行我们只需要用来判断是否有解即可。

递推

3777. 砖块

95. 费解的开关

Yuleo

交流频道

加入我们的社群讨论分享