吃糖果

单身狗II

路径总数

<pre><code>&#x27;&#x27;&#x27; 运用动态规划思想，每一格的步数等于左边格子和下边格子的方案和 每次绕过(x,y)这一点，将这一点的方案数设置为0 &#x27;&#x27;&#x27; dp = [[1 for _ in range(n)] for _ in range(m)] dp[x - 1][y - 1] = 0 for j in range(1, n): if 0 == x - 1 and j == y - 1: continue     dp[0][j] = dp[0][j - 1] for i in range(1, m): if i == x - 1 and 0 == y - 1: continue     dp[i][0] = dp[i - 1][0] for i in range(1, m): for j in range(1, n): if i == x - 1 and j == y - 1: continue         dp[i][j] = dp[i - 1][j] + dp[i][j - 1] print(dp[-1][-1])</code></pre>

<div>L=[[0 for i in range(n)]for j in range(m)] for i in range(m-1,-1,-1): &nbsp;&nbsp;&nbsp; if i==m-x and y-1==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp; L[i][0]=1 for j in range(n): &nbsp;&nbsp;&nbsp; if m-x==m-1 and j==y-1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break &nbsp;&nbsp;&nbsp; L[m-1][j]=1</div><div>for i in range(m-2,-1,-1): &nbsp;&nbsp;&nbsp; for j in range(1,n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i==m-x and j==y-1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pass &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; L[i][j]=L[i+1][j]+L[i][j-1] print L[0][n-1]</div>

一个非常拧巴的规划

# 总共走了m+n-2步，其中向左m-1步，使用排列组合公式就行了 def An(num): &nbsp; &nbsp; n = 1 &nbsp; &nbsp; for i in range(1,num+1): &nbsp; &nbsp; &nbsp; &nbsp; n *= i &nbsp; &nbsp; return n def C(m,n): &nbsp; &nbsp; &nbsp; &nbsp; return An(n)//An(m)//An(n-m) m,n,x,y = m-1,n-1,x-1,y-1 print(C(m,m+n)-C(x,x+y)*C(m-x,m+n-x-y))

使用排列组合，超级简单

lst=[[0]*n for i in range(0,m)] for i in range(0,n): &nbsp; &nbsp; if 0==x-1 and i==y-1: &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp; &nbsp; lst[0][i]=1 &nbsp; &nbsp;&nbsp; for i in range(0,m): &nbsp; &nbsp; if 0==y-1 and i==x-1: &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp; &nbsp; lst[i][0]=1 for i in range(1,m): &nbsp; &nbsp; for j in range(1,n): &nbsp; &nbsp; &nbsp; &nbsp; if i==x-1 and j==y-1: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pass &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lst[i][j]=lst[i-1][j]+lst[i][j-1] print lst[i][j]

规划

首先绘制成m*n的表格，起点所在行和列上的点的路径方式都只有一种，全标1之后在一个方格中，右上角的点的路径方式是左上和右下的和如是反复累加即得起点至终点的全部路径方式减去经过特殊点的路径方式即可<pre class="prettyprint lang-py linenums">mid = []
for item in xrange( n ) :
 mid.append( 1 )
metrix = []
for item in xrange( m ) :
 metrix.append( mid[ : ] )
for xo in xrange( 1 , m ) :
 for yo in xrange( 1 , n ) :
 metrix[ xo ][ yo ] = metrix[ xo - 1 ][ yo ] + metrix[ xo ][ yo - 1 ]
def route( a , b ) :
 return max( metrix[ a - 1 ][ b - 1 ] , 1 )
print route( m , n ) - route( x , y ) * route( m - x + 1 , n - y + 1 )</pre>

用了小学奥数的思路

这题的x和y指哪个方向？？？？？ 竟然说我越界。。。#m = 5 #n = 4 #x = 2 #y = 3 grid = [['.']*n for i in range(m)] grid[y][x] = '#' dp = [[0]*n for i in range(m)] def solve(row, col): &nbsp; &nbsp; if dp[row][col] != 0: &nbsp; &nbsp; &nbsp; &nbsp; return dp[row][col] &nbsp; &nbsp; if row == m-1 and col == 0: &nbsp; &nbsp; &nbsp; &nbsp; return 1 &nbsp; &nbsp; elif row == y and col == x: &nbsp; &nbsp; &nbsp; &nbsp; return 0 &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; if col-1 &gt;= 0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[row][col] += solve(row, col-1) &nbsp; &nbsp; &nbsp; &nbsp; if row+1 &lt; m: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[row][col] += solve(row+1, col) &nbsp; &nbsp; return dp[row][col] res = solve(0, n-1) print(res) &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;

明显动态规划, 然而。。。

虽然知道是bfs，但是不知道使用了什么测试用例，本地的测试都可以，但是过不了<pre class="prettyprint lang-py linenums">rsl = 0
directions = [(0,-1),(1,0)]
def bfs(m,n,x,y,cur):
	global directions
	if cur[0] == n-1 and cur[1] == 0:
		global rsl
		rsl += 1
		return
	for d in directions:
		new_x = cur[0] + d[0]
		new_y = cur[1] + d[1]
		if new_x &lt; n and new_y &gt;= 0:
			if new_x == x and new_y == y:
				continue
			else:
				bfs(m,n,x,y,(new_x, new_y))


cur = (0,m-1)
bfs(m,n,x,y,cur)
print rsl </pre>

广度优先搜索

<pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'宋体';font-size:12.0pt;">....
....
....
..#.
z...</pre><pre style="background-color:#2b2b2b;color:#a9b7c6;font-family:'宋体';font-size:12.0pt;">z是坐标原点， x，y没有影响的反正对称不影响</pre>

第138题：路径总数

最大整数

最长回文子串可不简单

新年祝福

阶乘