最近在复习动态规划问题，在处理挖金矿问题的时候发现网上以python实现的代码很少，于是自己整理一份。
问题描述：漫画图解
公式和讲解都在上面链接的网页里面，有一点需要说明他的图片结果是错的：
我自己手写了一份：
代码不知道对错，没有用java去写，直接上代码，注释写的自认为比较全，不会的好好理解下。
import copydef good(n,w,g=[],p=[]):# n为金矿数，w为人数，g为金矿数组，p为人数数组arr = [0]*wfor i in range(w):if (i+1)>=p[0]: # i为坐标， i+1为人数arr[i] = g[0]res = copy.deepcopy(arr) #深copyprint(res)# 上面为只有一个金矿的情况for i in range(1,n):# 金矿数for j in range(w): # 人工数if (j+1)<p[i]:# j为坐标， j+1为人数arr[j] = res[j] #和上一次情况相同else:t = 0 if (j-p[i])<0 else j-p[i] #防止负数取到后面的值arr[j] = max(res[j],res[t]+g[i]) #挖和不挖第i座金矿比较取大#res[t]+g[i] 为 挖第i座金矿的情况，res[已有人数 - 第i座所需人数]+第i座金子g[i]res = copy.deepcopy(arr)print(res)return res.pop()if __name__ == '__main__':res = good(5,10,[400,500,200,300,350],[5,5,3,4,3])print(res)
用到了深copy，不理解的去Baidu查一下，python里有拷贝，浅拷贝和深拷贝。
另外，有什么错误的地方欢迎大家指出。
