月饼节快乐

吃糖果

k差等数

<pre><code>dp = [[0 for _ in range(10)] for _ in range(n)] dp[0] = [0] + [1] * 9 for i in range(1, n): for num in range(10): if num + k &lt;= 9:             dp[i][num] += dp[i-1][num+k] if num - k &gt;= 0:             dp[i][num] += dp[i-1][num-k] print(9 if k == 0 else sum(dp[-1]))</code></pre>

lst=[[0]*10 for x in range(0,n)] for i in range(1,10): &nbsp;&nbsp;&nbsp; if i-k&gt;=0 or i+k&lt;10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[0][i]=1 for i in range(1,n): &nbsp;&nbsp;&nbsp; for j in range(0,10): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if k==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]=lst[i-1][j] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if j-k&gt;=0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]+=lst[i-1][j-k] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if j+k&lt;=9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]+=lst[i-1][j+k] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; print sum(lst[n-1])

mark class: class klist:&nbsp;&nbsp;&nbsp; def __init__(self,step,length): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; self.__step=step &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; self.__length=length &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; def outcount(self): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; k=self.__step &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; n=self.__length &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst=[[0]*10 for x in range(0,n)] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for i in range(1,10): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i-k&gt;=0 or i+k&lt;10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[0][i]=1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for i in range(1,n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for j in range(0,10): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if k==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]=lst[i-1][j] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if j-k&gt;=0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]+=lst[i-1][j-k] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if j+k&lt;=9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; lst[i][j]+=lst[i-1][j+k] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return sum(lst[n-1]) t=klist(k,n) print t.outcount()

规划路子，特殊情况注意k=0

def f(a,b):     l=list(str(a)) for i in range(len(l)-1): if abs(int(l[i])-int(l[i+1])) == b: return True l=[] for i in range(10**(n-1),10**n): if f(i,k)==True:         l.append(i) print(len(l))

超时了 希望大神帮忙优化

#参考别人的解法，动态规划方法 L=[[0]*10 for x in range(n)]#L[i][j]表示j出现在第i位上的可能性 for i in range(1,10):#第0位为i的可能性 &nbsp; &nbsp; if i+k&lt;10 or i-k&gt;=0: &nbsp; &nbsp; &nbsp; &nbsp; L[0][i]=1 for i in range(1,n): &nbsp; &nbsp; for j in range(10):#第i位为j的可能性 &nbsp; &nbsp; &nbsp; &nbsp; if k==0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]=L[i-1][j] &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j+k&lt;10: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]+=L[i-1][j+k] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j-k&gt;=0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]+=L[i-1][j-k] print sum(L[n-1])

参考别人的解法，动态规划方法

这个题目实际上使用的方式应该就是迭代更新，有意义的数字只有当前的最后一位，所以我只保留了最后一位去计算出结果；代码如下<pre class="prettyprint lang-py linenums">#n = 2
#k = 3
dic = {i:1 for i in range(1,10)} #初始化为[1,2,3,,4,..9]

i = 1
while i &lt; n:
	tmp = {i:0 for i in range(10)} #有计算出结果为0-9的分别的个数
	for key in dic.keys(): 
		if dic[key] != 0:
			subtmp = key - k #判断是否符合条件
			addtmp = key + k
			if subtmp &gt;= 0:
				tmp[subtmp] += dic[key] #符合的话就加入
			if addtmp &lt;= 9:
				tmp[addtmp] += dic[key]
	dic = tmp
	i += 1

#print dic
rsl = 0
for value in dic.values():
	rsl += value

print rsl</pre>

第140题：k差等数

单词接龙

365 Or 366？

LTC-男人八题之三：旅游线路问题

排队