基因串

木棒问题

地板覆盖

这个主要是参考了http://1439154.blog.51cto.com/1429154/1263157参考上面的知道，这个是一个动太规则的问题，这个方程是DP(i,j) = sum (DP(i-1, x), x &amp; j)，公式里面的sum表示总和，x表示所有列（0,1,.. ,n-1），然后 &amp;表示状态兼容，也就是这两个状态可以同时出现；在运算的时候，其实是根据上一行的各个状态来计算出本行的对应状态（有的位置已经被上一行设定了），主要是测试哪些位置可以放一个横着的块；，然后得到对应的状态，这种状态的可能性就是可以与这种状态兼容的上一行所有的状态的可能性之和 <pre class="prettyprint lang-py linenums">def dfs(row, state, col, pre_num):
	global n
	if col &gt;= n-1: #如果已经到了最后一个或是最后一个已经过了的话，就直接更新这种状态下的可能性
		dp[row][state] += pre_num
		return
	# let empt
	dfs(row, state, col + 1, pre_num)
	# 这里是將本位置和下一列的位置并一起，放一个横放的，，state &amp; (1 &lt;&lt; col)是用于判断是否这样放后col位置不会是已经放了块的（上一行竖着放的那个）01 &amp; 10 =9
	if (col &lt;= n - 2) and (state &amp; (1 &lt;&lt; col) == 0) and (state &amp; (1 &lt;&lt; (col+1)) == 0):
		dfs(row, state | (1 &lt;&lt; col) | (1 &lt;&lt; (col +1)), col + 2, pre_num)

#n = 4
m = 3
if n % 2 == 0:
	if n &gt; m: #这里主要是优化了一下，进行状态的压缩，因为状态越少的话，性能会更快，进行了一步的改进；没有这一步的话，无论是内存上还是运行时间上都会很大开销
	 n, m = m, n
	dp = [[0 for i in range((1 &lt;&lt; n) )] for j in range(m)]
	dfs(0, 0, 0, 1) #初始化第一行
	for i in xrange(1, m):
		for j in xrange(0, 1&lt;&lt;n): # state
			if dp[i-1][j] != 0:
				pre_num = dp[i-1][j]
				state = (~j) &amp; ((1 &lt;&lt; n) -1) #这里先对j取反，是取这个位置下的上一行的状态，状态总有1 &lt;&lt; n总可能性，取反后可以得到本行的已经放了块的（上一行在j这个状态上没有放块的是0，对应下来本行就是1）
				dfs(i, state, 0, pre_num)
			else:
				continue

	print dp[m-1][(1&lt;&lt;n) - 1]
	#print dp
else:
	print 0</pre>

优化了一下内存，就过了

参考：http://1439154.blog.51cto.com/1429154/1263157代码如下<pre class="prettyprint lang-py linenums">def dfs(row, state, col, pre_num):
	global n
	if col &gt;= n-1:
		dp[row][state] += pre_num
		return
	# let empt
	dfs(row, state, col + 1, pre_num)
	# put a 11 to the 下面的state &amp; 1 &lt;&lt; col是为了保证本行横放的块不会影响到本行已经被上一行竖放的地方，01 &amp; 10 = 0
	if (col &lt;= n - 2) and (state &amp; (1 &lt;&lt; col) == 0) and (state &amp; (1 &lt;&lt; (col+1)) == 0):
		dfs(row, state | (1 &lt;&lt; col) | (1 &lt;&lt; (col +1)), col + 2, pre_num)

#n = 2
m = 3
if n % 2 == 0:
	dp = [[0 for i in range((1 &lt;&lt; n) )] for j in range(m)]
	dfs(0, 0, 0, 1)
	for i in xrange(1, m):
		for j in xrange(0, 1&lt;&lt;n): # state
			if dp[i-1][j] != 0:
				pre_num = dp[i-1][j]
				state = (~j) &amp; ((1 &lt;&lt; n) -1) # 取反了为了得到i行已经放了块的地方，然后 1 &lt;&lt; n -1是为了得到它的数字，因为直接取反后是得到了负数
				dfs(i, state, 0, pre_num)
			else:
				continue

	print dp[m-1][(1&lt;&lt;n) - 1]
	#print dp
else:
	print 0</pre>

第121题：地板覆盖

变态超级楼梯

新年祝福

2017#新年快乐#2017

加油站