4パス単純DP
10926 ワード
DP類の問題はサブ問題(状態)を探し当てて、それから転移方程式を探し当てて、OKです
one:initialization(初期化)
two:recurrence(プッシュ)
多項式時間、余分なストレージスペースが必要
#dp
#likes matrixchain
#according to two point's distance to recurrence
class Solution:
# @return a string
def longestPalindrome(self, s):
length = len(s)
p = [[0 for col in range(length)] for row in range(length)]
for i in range(len(s)):
p[i][i] = 1
if(i<(length-1) and s[i] == s[i+1]):
maxlenth = 2
p[i][i+1] = 1
start = i
for i in range(3,length+1):
for j in range(length-i+1):
k = j + i - 1
if(s[j]==s[k] and p[j+1][k-1] == 1):
maxlenth = i
p[j][k] = 1
start = j
return s[start:start+maxlenth]
if __name__ == '__main__':
s = Solution()
test_str = 'abcba'
print s.longestPalindrome(test_str)
#dp least number coins
#one:overlapping subproblem
#two:optimal substructure
class Solution:
# @return a string
def least_number_coin(self, s, v):
#first initialization
min_number = [1000000]*(s+1)
min_number[0] = 0
#And then,recurrence
#time need O(n^2),and additional time O(n) to save the subproblem's temp solution
for i in range(1,s+1):
for j in range(len(v)):
print i,v[j]
if(v[j]<=i and (min_number[i-v[j]]+1 < min_number[i])):
min_number[i] = min_number[i-v[j]]+1
print min_number
return min_number[s]
if __name__ == '__main__':
s = Solution()
money = 11
v = [1,3,5]
print s.least_number_coin(money,v)
#dp
#time O(n^2),addtional O(n) to save temp result
class Solution:
# @return a string
def LIS(self,v):
print v
d = [1]*(len(v))
print d
for i in range(len(v)):
for j in range(i):
print i,j
if (v[j]<=v[i] and d[j]+1>d[i]):
d[i] = d[j]+1
print d
print max(d)
if __name__ == '__main__':
s = Solution()
v = [5,3,4,8,6,7]
s.LIS(v)
#dp
class Solution:
# @return a string
def max_number_apples(self, apples, n, m):
print apples
s = [[0 for col in range(m)] for row in range(n)]
for i in range(n):
for j in range(m):
if(i==0 and j==0):
s[i][j] = apples[0][0]
elif(i==0 and j>0):
s[i][j] = s[i][j-1]+apples[i][j]
elif(j==0 and i>0):
s[i][j] = s[i-1][j] + apples[i][j]
else:
if(s[i-1][j]>s[i][j-1]):
s[i][j] = s[i-1][j] + apples[i][j]
else:
s[i][j] = s[i][j-1] + apples[i][j]
print s
return s[n-1][m-1]
if __name__ == '__main__':
s = Solution()
n = 3
m = 4
apples = [[0 for col in range(m)] for row in range(n)]
k = 1
for i in range(n):
for j in range(m):
apples[i][j] = k
k = k + 1
s.max_number_apples(apples,n,m)
one:initialization(初期化)
two:recurrence(プッシュ)
多項式時間、余分なストレージスペースが必要