1.题目描述

https://www.hackerrank.com/challenges/lego-blocks

2.解法分析

这题乍看一下觉得应该可以用动态规划来做，但是却死活想不到最优子结构，在网上搜了一下，找到一个英文的描述，整理如下。

首先需要明白一点，稍微复杂一点的动态规划不一定能直接找到最优子结构，可能内嵌一些其他的最优子结构，比如说这题，我们需要得到如下的知识：

• layerCom[w] : 表示高度为 1 ,宽度为 w 的墙有多少种，先暂且忽略solid structure这个约束

layerCom[1] = 1  layerCom[2] = 2  layerCom[3] = 4 layerCom[4] = 8 这个是可以直接枚举获得的 当w > 4 时，一直layerCom[w] = layerCom[w-1] +layerCom[w-2] + layerCom[w-3]+ layerCom[w-4] ,其中，layerCom[w-i]表示最左一块砖是宽度为 i 的情况。

• wholeCom[w][h] : 表示宽度为 w，高度为h的墙总共有多少种，也是先忽略solid structrue这个约束
  
  

  很显然，wholeCom[w][h] = power(layerCom,h)

• retCom[ w][h] ： 表示施加了solid structure这个约束时，宽度为w，高度为h的墙的种类，递推公式如下,其中

  表示以从右至左第i块条垂面作为切割面，左边是solid structure，右边是随意形状的种类

3.代码

不考虑modula的条件的代码如下：

#include <stdio.h> #include <string.h> #include <cmath> #include <stdlib.h> #include <iostream> #include <vector> using namespace std; int getCom(int w,int h); int main() {   /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int T; cin>>T; int i = 0; while(i<T) { int N,M; cin>>N>>M; cout<<getCom(M,N)<<endl; i++; } return 0; } int getCom(int w,int h) { vector<int> layerCom((w<4 ? 4:w),0); layerCom[0] = 1; layerCom[1] = 2; layerCom[2] = 4; layerCom[3] = 8; if(w > 4) { for(int i = 4;i<w;++i) layerCom[w-1]=layerCom[w-2] + layerCom[w-3] + layerCom[w-4] + layerCom[w-5]; }   vector<int>wholeCom(w,0); for(int i=0;i<w;++i)wholeCom[i]=(int)pow((double)layerCom[i],h);   vector<int> retCom(w,0); retCom[0] = 1;   for(int i = 1;i<w;++i) { retCom[i] = wholeCom[i]; for(int j = 1;j<=i;++j) { retCom[i] -= retCom[i-j]*wholeCom[j-1]; } }   return retCom[w-1]; }