步骤
(1)确定初始状态
(2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来
(3)确定边界条件。
例题
蓝桥杯——印章(python实现)
使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率
i表示买的印章数,j表示凑齐的印章种数
情况一:如果i<j,不可能凑齐印章,概率为0
情况二:如果j=1,dp[i][1] = n*((1/n)**i),凑齐一种印章,所有i个印章为一个种类,这一个种类有n种情况可选
情况三:凑齐j种印章。前面买了i-1个印章。可能前面i-1步凑够了j种印章,那么只用从j种里随意选出来一个dp[i-1][j]*j*p;可能前面i-1步凑够了j-1种印章,那么从剩下的n-j+1种里选出来一个dp[i-1][j-1]*(n-j+1)*p,因此为dp[i][j] = dp[i-1][j]*j*p+dp[i-1][j-1]*(n-j+1)*p
strs = input().strip().split()
n = int(strs[0])
m = int(strs[1])
# 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率
dp = [[0]*(n+1) for _ in range(m+1)]
p = 1.0/n
for i in range(1,m+1):
for j in range(1,n+1):
# 如果i<j,不可能凑齐印章
if i<j:
dp[i][j] = 0
# 如果凑齐一种印章
elif j==1:
dp[i][1] = n*(p**i)
# 凑齐j种印章:可能前面i-1步凑够了j种印章,那么只用从j种里随意选出来一个;
# 可能前面i-1步凑够了j-1种印章,那么从剩下的n-j+1种里选出来一个
else:
dp[i][j] = dp[i-1][j]*j*p+dp[i-1][j-1]*(n-j+1)*p
print('%.4f'%(dp[m][n]))
蓝桥杯——算法训练 拿金币
使用dp记录状态,dp[i][j]表示在arr[i][j]可以拿到的最多金币数。
情况一:如果i=j=0,那么此位置最多拿到金币数dp[0][0]=arr[0][0]
情况二:如果i=0,那么无法从上方转移,只能从左边转移到arr[0][j]。dp[0][j] = dp[0][j - 1] + arr[0][j]左边位置的最大金币数加上当前位置arr[0][j]的金币数
情况三:如果j=0,那么无法从左方转移,只能从上边转移到arr[i][0]。dp[i][0] = dp[i - 1][0] + arr[i][0]上边位置的最大金币数加上当前位置arr[i][0]的金币数文章来源:https://www.toymoban.com/news/detail-468892.html
情况四:如果i,j != 0,dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j],当前位置金币数arr[i][j]加上左边和上边dp中最大的一个 max(dp[i - 1][j], dp[i][j - 1]) 文章来源地址https://www.toymoban.com/news/detail-468892.html
n = int(input())
strs = [(input()).strip().split() for _ in range(n)]
arr = []
for i in range(n):
temp = []
j = 0
while j < len(strs[i]):
temp.append(int(strs[i][j]))
j += 1
arr.append(temp)
dp = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == 0 and j == 0:
dp[0][0] = arr[0][0]
if i == 0:
dp[0][j] = dp[0][j - 1] + arr[0][j]
if j == 0:
dp[i][0] = dp[i - 1][0] + arr[i][0]
if i != 0 and j != 0:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j]
print(max(max(dp)))
到了这里,关于DP算法:动态规划算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!