温馨提示:文本由机器自动转译,部分词句存在误差,以视频为准
00:00
今天我们看一下这个一种非布纳切的变种,是覆盖矩形,这是第十题扩展出来的第二小题。为什么说是非纳切的变种,因为它这个规律特别有意思。我们看一下,它是要用一个二乘一的小矩形横着放或者竖着放去覆盖更大的矩形,比如说这个矩形是用二乘N来建立的,既然要用N个小的二乘一的矩形去无数次的覆盖,它有多少种覆盖的方法,那这种方法呢?可以抽象成一个思路,大家可以找一下规律,比如说当NV1的时候,它就一种,当NV2的时候,横着或竖着是两种,但我们数量变多的时候,我们可以通过画图来理解一下,比如说当DN等于三的时候,当我们已经占用了一层这层第三层第三节的时候,选择横着放,那我们剩下的是两节的内容,那就还剩两种方。
01:29
吧,那这样的话,再看下面这个,他如果是选择竖着放的话,那实际上我们可选空间就只剩了一种。因此呢,我们可以把这种问题抽象成我们把最后一集选择横着放还是竖着放,这也就直接影响了我们前面的空间,还有还有几种方法的可选项,最后把这个重合相加,那也就扩展到DN种DN级的情况,比如我们DN级如果用了一级。
02:05
或者是用了两级,那我们就可以推算出来前面的N减一有多少种覆盖的方法,或者是前面的N减二有多少种覆盖的方法,那我们之前嗯,就是这种思想,然后先来写一下,首先他一定要符合我们这个边界范围,就要把他这个目标的target小于等于二的情况,就直接返回他这个target,他这个虽然是非布纳奇的规律,但是前面并不是从一一开始,而是就是一二开始,相当于少了一期。现在呢,我们设立两个指针,就是当前我们前面一个,后面一个不断的去向后变离,这跟刚才那个递归来比的好处就是它不会出现那种时间或者空间的超时情况,它这个时间空间复杂度还是比较低的,那我们现在这个放循环是从三开始的。
03:33
他一直到别利老师这个target的白加加,这时候记录一下,每次大哥这个连接空间去记录一下中间的生成的变量,每次把这个后边的值替换成更新,向后更新,然后把它。
04:09
前面的那个值就变成了当前,嘉禾最后返回整个第一个值就是我们想要的,来测试一下。
我来说两句