python 动态规划问题解析(背包问题和最长公共子串)_python_

class SolutionBag: def valuableBag(self,optionalList,sizeBig): #创建网格 grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)] #从行列序号1开始计数 column = 1 for v in optionalList.values(): optionalWeight,optionalPrice = v for row in range(sizeBig): if optionalWeight > row+1: grid[column][row+1] = grid[column-1][row+1] else: grid[column][row+1] = max(grid[column-1][row+1],optionalPrice+grid[column-1][row+1-optionalWeight]) column += 1 return grid#SolutionBag().valuableBag({"A":(1,15),"B":(3,20),"C":(4,30)},4)

#伪代码 #字母相同则左上方+1 if word1[i] == word2[j] : cell[i][j] = cell[i-1][j-1] +1 else: cell[i][j] = max(cell[i][j-1],cell[i-1][j])

class SolutionLengthS: def longestLength(self,str1,str2): grid = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)] for i in range(len(str2)): for j in range(len(str1)): if str1[j] == str2[i] : grid[i+1][j+1] = grid[i][j] + 1 else: grid[i+1][j+1] = max(grid[i+1][j],grid[i][j+1]) return grid