这是Matrix67.com的递推专项训练的题目,感觉很好.
*题一:用1 x 1和2 x 2的磁砖不重叠地铺满N x 3的地板,共有多少种方案?
先设一个f[i]表示i*3的地板铺的方法f[1]=1;f[2]=3;
i*3的地板数是这样得到的:(i-1)*3的地板比i*3的地板少的地方全铺上1*1的瓷砖,这有一种铺法;
或者在(i-2)*3的地板比i*3的地板少的地方铺上2*2的瓷砖和2个1*1的瓷砖,这有两种铺法;
*题二:从原点出发,一步只能向右走,向上走或向左走.恰好走N步且不经过已走的点共有多少种走法?
这个我没想出来,看题解才弄明白.
先设一个f[i]表示恰好走i步且不经过已走的点 共有的走法.
如果向上走,不会出现经过已走的点;如果向左或右,上一步不能是向右或左.
引用题解上的一句话:/*
这一步的选择数= (3*上一步的所有选择中向上走的选择数) + (2*上一步的所有选择中向左,右走的选择数).上一步的所有选择中向上走的选择数"实际上就是"上上步的所有选择数"即d[i-2]
还有一点,就是"上一步的所有选择中向左,右走的选择数" 等于 "上步所有的选择数(即f[i-1])-上步向上的选择数"
题解上共有五题,都很好,大家可以去这里看看: