魂魄妖梦我老婆:有同学问我砌墙的思路,评论里也有问的,这里说一下我当时的思路吧: 设为砌规格为的墙的总砌法数,用DP方法在一维递推,很容易得到。因为不同高度的层与层是不影响的,根据乘法原理有。 再设为规格为不带缝的并且内部不含有任何从顶到底线段的砌法之和。我们考虑出现从顶到底的线段的砌法:如果我们允许内部出现线段,那么最后一条线段出现在水平位置为的地方的砌法为: (水平位置小于的部分任意摆放,后面的则必.须无缝)。由于在不同时的情况是互斥的,我们有 ,则我们的递推公式为 ,DP即可。
投递字节跳动等公司10个岗位 >
0 点赞 评论 收藏
分享
关注他的用户也关注了: