前言：
如今小伙伴们对“动态规划棋盘算法”大体比较珍视，看官们都需要分析一些“动态规划棋盘算法”的相关文章。那么小编同时在网摘上网罗了一些对于“动态规划棋盘算法””的相关知识，希望我们能喜欢，大家快快来了解一下吧！在之前介绍的排序算法中，二分搜索、合并排序、快速排序都是用分治方法排序的。类似于数学归纳法，思想还是很简单的。
案例：
在一个2的k次方乘以2的k次方个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格，且称该棋盘为一个特殊棋盘。显然特殊方格在棋盘上出现的位置有4的k次方种情形。因为对任何k>=0，有4的k次方种不同的特殊棋盘。如图（a)所示。
在棋盘覆盖问题中，要用4种不同形态的L型骨牌（b图所示）覆盖一个给定的特殊棋盘上除特殊方格以外所有方格，且任何2个L型骨牌不得重叠覆盖。
分治策略：
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，这三个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1×1棋盘。
图解过程：
具体算法：
图片和算法参考网上资源，若有侵权立即删
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #动态规划棋盘算法
