动态规划学习（持续更新）

本篇博文主要记录动态规划DP这一块的学习。

印章(6.27)

问题描述：共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。（1≤n，m≤20）
输入格式：一行两个正整数n和m
输出格式：一个实数P表示答案，保留4位小数。

思考1：
概率论？！分类讨论
1）当m<n时，集齐的概率为0
2）当m>n时，买的m张印章，每张有n种可能，分母：n的m次方；分子：(C_m^n) * (C_n m-n)（m张印章中，有n张是图案不同的，剩下的m-n张随意）。

思考2：
动态规划解题步骤：

1）设置状态，即数组
dp[i][j] = 印章数目为i、集齐j种印章的概率
dp[1][1] = 1
dp[i][1] = (1/n)^(i-1)
i < j时，dp = 0

2）确定状态转移方程
找状态之间的关系，从手里有（i-1）枚印章到 i 枚印章时，有两种情况，第一种，拿到的这枚印章种类手里已经有了，此时 dp[i][j] 表示手里已经有 j 种印章了，因此上个状态也只有 j 种印章，即 dp[i-1][j] 。dp[i][j] = dp[i-1][j] * j/n；第二种，拿到的这枚印章种类手里还没有，所以上个状态表示为dp[i-1][j-1]，一共有n种印章，前面已经取了（j-1）种，而现在取的和前面没有重复，因此取的是n-(j-1)中的其中一个。

3）代码实现

n,m = map(int,input().split())
dp = [[0 for i in range(n+1)]for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if (i < j):
            dp[i][j] = 0
        elif (j == 1):
            dp[i][j] = (1/n)**(i-1)
        else:
            dp[i][j] = (dp[i-1][j])*(j*1.0/n) + (dp[i-1][j-1])*((n-j+1)*1.0/n)
print("%.4f"%(dp[m][n]))   

拿金币（6.28）

问题描述：有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入格式：第一行输入一个正整数n。以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式：最多能拿金币数量。

思考1：
n*n的方格应该用一个数组表示，dp[i][j]表示i行j列的金币数量，想要求出能拿金币最多的数量，每次移动做选择的时候，比较右边还是下边的金币数量大，哪边大就往哪边移动，直到不能移动为止（没有向右也没有向下的选择，即边界处）

思考2：
状态转移方程
dp[i][j] = max((dp[i][j-1]+dp[i][j]),(dp[i-1][j]+dp[i][j]))

代码

n = int(input())
rect = []

for i in range(n):
    rect.append(list(map(int, input().split())))
    
#将边界的数单独算出来    
for i in range(1,n):
    rect[0][i] =rect[0][i] + rect[0][i-1]
    
for i in range(1,n):
    rect[i][0] = rect[i][0] + rect[i-1][0]
    
for i in range(1,n):
    for j in range(1,n):
        rect[i][j] = max(rect[i][j-1],rect[i-1][j]) + rect[i][j]
                
print(rect[-1][-1])