【动态规划】

使用场景：

有方向（无环，无相反方向）

求最优值，求可行性，只求方案总数

题型分类：

坐标型，前缀型（划分型：一个字符串划分，匹配性：两个字符串匹配），背包型，区间型，博弈型，树型，状态压缩型（TSP问题）。

坐标型，可行性+最值

需要注意的是：这些点都在当前点的左边，因此需要按“列”遍历。

grid = [[0,0,0,0],[0,0,0,0],[0,0,0,0]]
n=len(grid)
m=len(grid[0])
dp=[[float('inf')]*m for _ in range(n)]
dp[0][0]=0

for j in range(m):
    for i in range(n):
        for dx,dy in [(-1,-2),(1,-2),(2,-1),(-2,-1)]:
            x=i+dx
            y=j+dy
            if 0<=x 
 
博弈性，可行性
 
a = [3,2,1,0,4]
n=len(a)
dp=['false']*n
dp[0]='true'
for i in range(1,n):
    for j in range(i):
        if dp[j]=='true' and a[j]>=i-j:
            dp[i]='true'
            break

print(dp)
 
前缀型，最值
 
LintCode 炼码
 
第一种：bool型
 
n=len(a)
dp=[[False]*(m+1) for i in range(n+1)]
dp[0][0]=True
for i in range(1,n+1):
    dp[i][0]=True
    for j in range(m+1):
        if j-a[i-1]>=0:
            dp[i][j]=dp[i-1][j] or dp[i-1][j-a[i-1]]
        else:
            dp[i][j]=dp[i-1][j]
for i in range(m,-1,-1):
    if dp[n][i]==True:
        return i
        break
 
注意：前缀和类型是要算上前0项的，故要建立n+1，m+1的dp二维列表
 
第二种：
 
a=[3,4,8,5]
m=10
n=len(a)
dp=[[0]*(m+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        if j>=a[i-1]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1]]+a[i-1])
        else:
            dp[i][j]=dp[i-1][j]

print(dp[n][m])
 
第一种效率要比第二种高，因为逻辑运算要比算术运算快。