91酷站字体下载频道

递推的思维构建与技巧实现

2021-4-29 20:07 发布

来自: 51CTO技术博客/ 语言 /
发布者: 705073012,如需商业用途或转载请与705073012联系,谢谢配合。

  递推是一种用若干步可重复运算来解决复杂问题的方法。

1.一维递推

1.1 问题描述

  有一个n层的楼梯,每次只可以向上爬1层或者2层,问爬完n层共有多少种不同的方式呢?

1.2 分析

  设f(n)表示n层楼总共不同的方式。
假设此时位于第i层,因为每次只能爬1层或2层,所以到第i层只有2种方式。

  •   从第i-1层爬上来。

  •   从第i-2层爬上来。

  所以得到递推公式为f(n)=f(n-1)+f(n-2)。前2项之和等于第3项,其实就是斐波那契数列,1,1,2,3,5,8,13,21...

1.3 代码实现

f[0]=1;f[1]=1;
for(inti=2;i<n;i++){
f[i]=f[i-1]+f[i-2]
}
cout<<f[n-1]<<endl;

1.4 空间优化

  每一步的递推只与前2步有关,所以只需要记录前2步的方案数,用滚动数组,而不需要开O(n)的空间。
手动赋值

intf[3];
f[0]=1;
f[1]=1;
for(inti=2;i<10;++i){
f[2]=f[1]+f[0];
f[0]=f[1];
f[1]=f[2];
cout<<f[2]<<endl;
}

  取模滚动

intf[3];
f[0]=1;
f[1]=1;
for(inti=2;i<10;++i){
f[i%3]=f[(i-1)%3]+f[(i-2)%3];
cout<<f[i%3]<<endl;
}

  如果只与前一个状态有关,比如f[n]=f[n-1]+1,可以用0,1滚动,这个在动态规划中会比较常用。

intf[2],t=0;
f[0]=1;
for(inti=2;i<10;++i){
t=1-t;
f[t]=f[1-t]+1;
cout<<f[t]<<endl;
}

  递推和动态规划最大的区别:递推的每一步是所有方案数的加和,而动态规划在每一步递推中,需要用来选取一个最优策略。本质其实都是通过重复的小规模子问题推导出大规模的结果。

1.5 时间优化

  斐波那契数列递推公式很简单,但数据很大时,效率就比较低,因为递推是O(n)复杂度。
通过矩阵公式变换可将加法变为乘法
如下将递推公式放入矩阵:

  假设:则:

  
可以通过矩阵幂乘快速求出,时间复杂度为,再带入上式即可获得数列值。
具体可以看另一篇递推优化-矩阵幂乘

2.多维递推

2.1 问题描述

  从原点出发,每次只能向东,向北,向西走,且不能走已经走过的地方,问走n步共有多少种不同的方式呢?

2.2 分析

  假设已经走到第i步,因为不能走已经走过的地方,那这一步能走的方式只会与上一步有关。因为每次走一步,要保证不走回头路,就保证不走上一步走过的地方就行了。

  每次有3个选择,即向东,向北,向西。

  •   第i-1步向东走,那么第步只能向北、向东。

  •   第i-1步向西走,那么第步只能向北、向西。

  •   第i-1步向北走,那么第步可以向北、向东,向西。

  一维的f[n]只能记录一个总数,而不能记录状态,所以要再多一维记录上一步走的状态。
设f[n][0], f[n][1], f[n][2]分别表示:第步向东、向西、向北走总共不同的方式。
则有如下递推关系:

  • f[n][0] = f[n - 1][0] + f[n - 1][2];
  • f[n][1] = f[n - 1][1] + f[n - 1][2];
  • f[n][2] = f[n - 1][0] + f[n - 1][1] + f[n - 1][2];

2.3 代码实现

intf[100][3]={0};
f[0][0]=1;
f[0][1]=1;
f[0][2]=1;

for(inti=1;i<n;++i){
f[i][0]=f[i-1][0]+f[i-1][2];
f[i][1]=f[i-1][1]+f[i-1][2];
f[i][2]=f[i-1][0]+f[i-1][1]+f[i-1][2];
}
cout<<f[n-1][0]+f[n-1][1]+f[n-1][2]<<endl;

2.4 进一步优化

  设第n步的总方案数为s[n], s[n]=f[n][0]+f[n][1]+f[n][2]。
s[n]=2f[n-1][0]+2f[n-1][1]+3f[n-1][2]。
s[n]=2s[n-1]+f[n-1][2]。
而f[n-1][2]=f[n-2][0]+f[n-2][1]+f[n-2][2]=s[n-2]。
得s[n]=2s[n-1]+s[n-2]。
所以对公式变形,也可以通过一维的方式完成递推,但这个关系无法直接通过建模构造出来。

3.图递推

3.1 问题描述

  在一个的二维地图中,一个人从左上角走到右下角,每次只能向右或者向下走,问到终点共有多少种不同的方式呢?

3.2 分析

  假设已经位于某个位置,因为只能向右或者向下走,那上一步只能从上或者从左走过来。
设f[i][j]表示走到坐标总共的方案数。
则f[i][j]=f[i-1][j]+f[i][j-]。

3.3 代码实现

intf[10][10]={0};
f[0][0]=1;
for(inti=0;i<n;++i){
for(intj=0;j<m;++j){
if(i-1>=0){
f[i][j]+=f[i-1][j];
}
if(j-1>=0){
f[i][j]+=f[i][j-1];
}
}
}

3.4 进一步思考

  要到达终点,一定要向下走n-1步,向右走m-1步。
把每一步组合在一起来看,其实问题就等价于在n+m-2步中选择n-1步向下走,或者选择m-1步向右走,通过排列组合公式就可以直接得到结果。

4.状态压缩递推

4.1 问题描述

  在一个的棋盘中放置棋子,有一些地方不能放置。要求放置棋子时任意2个棋子不能在同1行或同1列,问放置k个棋子有多少种不同的方式呢?

4.2 分析

  对于每1个位置,只会有2种情况,就是放或不放。在数据规模不大的情况下可以用DFS(深度优先搜索)枚举所有的情况就可以了。

  那有没有更好的方法呢?

  这个最终是要求方案总数,而不需要考虑每一步是否需要择优,所以是符合递推模型,接下来就是怎么找出递推关系。

  先分析一些隐含的规律,把问题理得更清晰:

  •   每1行或者每1列都只能放置1个棋子,所以按每一行来枚举放置方法。

  •   在尝试第i行时,每一个位置(i,j)能不能放置,不只是跟上一行有关,而是跟之前的所有行都有关。这就说明需要记录之前放置的方法,也就是状态。

  那怎么记录之前放置的方案状态呢,这就要用到状态压缩。
状态压缩:本质就是用二进制记录对应位置的2种状态,0表示不放,1表示放。

  对于n个位置,就可以用个十进制数来表示所有放置的方案。

  继续回到上面的问题,在尝试第i行时,能否放置跟之前的i-1行都有关,意味着需要记录之前所有行放置的状态。
但看下面2种情况,图1和图2对于在尝试放置第3行时,其实是等价的,前2列都是不能放置。也就是说这2种方案数是可以直接合并的,因为每1列也只能放一个,所以放置的方案状态也可以直接合并成一行。

  用f[i][j]表示前i行,放置方案为j总共的方案数。
第0行的过程如下:

  第1行的过程如下:

  如此递推求出n行,种放置方案的总数,。因为只能放置k个棋子,所以在种放置方案中找出刚好是k个棋子的方案,也就是对应的状态j转化为二进制时,有k个1。

4.3 二进制包含1的个数

  目标数n,通过n&(n-1)运算,包含多少个1就刚好进行多少次该运算,可以快速求出1的个数。

4.4 代码实现

  计算数n中包含1的个数

intcountOne(intn){
inttotal=0;
while(n>0){
total++;
n&=n-1;
}
returntotal;
}

  变量定义及初始化

inti,n,k,line[8],f[2][256],num[256];

for(i=0;i<256;++i)num[i]=countOne(i);

memset(f,0,2*256*4);
f[0][0]=1;
intj,c,now=0;

//棋盘读入
for(i=0;i<n;++i){
intt=0;
for(intj=0;j<n;++j){
t<<=1;
cin>>ch;
if(ch=='.')t+=1;
}
line[i]=t;
}

  核心递推

for(i=0;i<n;++i){
now=1-now;
for(j=0;j<256;++j)
if(num[j]<=k){
//第i行不放棋子
f[now][j]+=f[1-now][j];
//第i行放棋子
for(c=0;c<n;++c){
if((j&1<<c)==0&&(line[i]&1<<c)==0){
f[now][j|1<<c]+=f[1-now][j];
}
}
}
}

//枚举所有包含k个棋子的方案数
intans=0;
for(i=0;i<256;++i){
if(num[i]==k){
ans+=f[now][i];
}
}
cout<<ans<<endl;

5.总结

  递推最重要的思想,就是通过每一小步,找出与下一步之间的关系。关键在于思考问题的本质,对问题进行建模。常用f[i][j][k]等类似数组来记录,多一维就可以多记录一维状态信息,要思考上一步真正有多少个因素会影响当前步,那一般这些就是一定要记录的信息。

  关注我,涨知识,微信公众号:几何思维

  往期精彩回顾

  蚂蚁走迷宫

  老鼠与毒药

  通过6人介绍可以认识世界上任何一个人?

  

严禁发布广告
91酷站字体下载频道

联系
我们
/**/
返回顶部