ダイナミックプランニングの2:最長男シリーズ問題(計5題)

タイトル1:(最長同じアルファベットを求める)文字列のセットを与えて、大文字と小文字を含んで、同じアルファベットからなる最長男の列を求めて、アルファベットは大文字と小文字を区別しません.例えば、aAbbbBBcccCC最長子列:ccCC例えばddDDDDeeEEEeeeEEEeee最長子列:eeeEEEeeeEEEeee

    ：dp[i]  i             

     "aAbbBBcc"   ,      .
     a  A  b  b  B  B  c  c
     1  2  1  2  3  4  1  2

         :
if s[i] == s[i-1]: dp[i] = dp[i-1] + 1
if s[i] != s[i-1]: dp[i] = 1

python    :
def longestSameChars(s):
	if s == None : return None
	w = len(s)
	if w == 0 or w == 1 : return s
	dp = [ 1 for i in range(w) ]
	for i in range(1, w):
		if s[i].upper() == s[i-1].upper() : dp[i] = dp[i-1] + 1
		else : dp[i] = 1
	#                       
	end, maxd = 0, 0
	for i in range( len(dp) ):
		if dp[i] > maxd:
			maxd = dp[i]
			end = i
	sta = end - maxd + 1
	return s[sta : end + 1 ]

题目2:(最长の连続上升の子のシリーズの长さを求めます)1つの整数の配列を与えて、配列の中の最长子の列の长さを求めますいくらですか?例えば、1,4,3,6最長子列が3 6または1 4の長さが2である例えば、15,1,5,13,6,11,7,8最長子列が1,5,13の長さが3である

    :dp[i]  i          .

    [15, 1, 5, 13, 6, 11, 7, 8]  ,       .
    15  1  5  13  6  11  7  8
    1   1  2  3   1  2   1  2  (           )

         :
if nums[i] > nums[i-1] : dp[i] = dp[i-1] + 1
if nums[i] <= nums[i-1]: dp[i] = 1

python     :
def lengthOfContinueLIS(nums):
	if len(nums) == 0 : return 0
	dp = [ 0 for i in range( len(nums) ) ]
	for i in range( 1, len(nums) ):
		if nums[i] > nums[i-1] : dp[i] = dp[i-1] + 1
		else : dp[i] = 1
	return max(dp)

题目3:(最も长い上升の子のシリーズの长さを求めます)1つの整数の配列を与えて、配列の中の最も长い上升の子のシリーズの长さを求めますいくらですか?例えば、1,4,3,6最長子列が1 3 6または1 4 6の長さはいずれも3例えば:15,1,5,13,6,11,7,8最長上昇子系列が1,5,6,7,8の長さはいずれも5

    :dp[i]  i              .

   [10, 9, 2, 5, 3, 1, 7, 101, 18]  ,      .
    10  9  2  5  3  1  7  101  18
    1   1  1  2  2  1  3  4    4  (          )

    i,    i  ( 0 ~ i-1 ) i     dp      +1
         :
for j in range( i ):
	if nums[j] < nums[i] : dp[i] = max( dp[i], dp[j] + 1 )
	
python    :
def lengthOfLIS(nums):
	if len(nums) == 0 : return 0
	dp = [ 1 for i in range( len(nums) ) ]
	for i in range( 1, len(nums) ):
		for j in range( i ):
			if nums[j] < nums[i] : dp[i] = max( dp[i], dp[j] + 1 )
	return max(dp) 

題目4:(最長重複なし文字列の長さを求める)文字列を指定し、重複文字を含まない最長男列の長さを見つけてください.例1:入力:「abcabcbb」出力:3説明:重複文字のない長男列が「abc」であるため、その長さは3である.例2:入力:「bbbb」出力:1説明:重複文字のない最長子列は「b」であるため、その長さは1である.例3:入力:「pwwkew」出力:3説明:重複文字のない最長子列は「wke」であるため、その長さは3である.

    : dp[i] i                

     "abcabcbb"   ,      .
    a  b  c  a  b  c  b  b
    1  2  3  3  3  3  2  1  (            )

      :
for j in range( i - 1, -1, -1 ):
	if s[i] != s[j] : dp[i] += 1
	else : break
	
python    :
def lenghtOfLongestSubstring(s):
	if len(s) == 0 or len(s) == 1 : return len(s)
	dp = [ 1 for i in range( len(s) ) ]
	for i in range( 1 , len(s) ):
		endfor = i - 1 - dp[i-1]
		for j in range( i - 1, endfor, -1 ):
			if s[i] != s[j] : dp[i] += 1
			else : break
	return max(dp)

タイトル5:(最長交替子系列の長さを求める)隣接する数字の大きさ関係は昇順降順が交代する(最初は昇順でも降順でもよい)、wiggle sequenceと呼ばれる.例えば[1,7,4,9,2,5,]はwiggle sequenceである.しかし[1,4,7,2,5]および[1,7,4,5,5]はそうではない.配列を与えて、その最長wiggle sequenceサブシリーズを求める.

    : dp[i] i             

   [10, 9, 2, 5, 5, 1, 7, 11, 8]  ,      .
     10  9   2   5   5   1   7   11   8
  st 0  -1  -1   1   1  -1   1   1   -1  (  st   [1:  ,-1:  ,0:  ]  )
  dp 1   2   2   3   3   4   5   5    6  (  dp          )

      (   ):
if nums[i] == nums[i-1] : 
	st[i], dp[i] = st[i-1], dp[i-1]
if nums[i] > nums[i-1]:
	st[i] = 1
	if st[i-1] == 1 : dp[i] = dp[i-1]
	if st[i-1] == -1 : dp[i] = dp[i-1] + 1
if nums[i] < nums[i-1]:
	st[i] = -1
	if st[i-1] == -1 : dp[i] = dp[i-1]
	if st[i-1] == 1 : dp[i] = dp[i-1] + 1

python    :
def wiggleMaxLenght(nums):
	if nums == None : return None
	w = len(nums)
	if w == 0 or w == 1 : return w
	dp , st = [ 1 for i in range(w) ], [ 0 for i in range(w) ]
	for i in range( 1, w ):
		if nums[i] == nums[i-1] : 
			st[i], dp[i] = st[i-1], dp[i-1]
		elif nums[i] > nums[i-1]:
			st[i] = 1
			dp[i] = dp[i-1] if st[i-1] == 1 else dp[i-1] + 1
		else:
			st[i] = -1
			dp[i] = dp[i-1] if st[i-1] == -1 else dp[i-1] + 1
	return dp[-1]