划分类动态规划

1 题型分析

1.1 题型

• 单序列划分为若干段，(不重叠的subarray)
• 段数不限制或者限制k段
• 每一段满足一定的性质或者整体满足一定的要求

  1.2 解法

• 类似于序列型动态规划，但是要加上段数信息
• 一般用dp[i][j]表示和记录前i个元素分成j段的性质
• 最后一步，最后一段从后往前看！

2 买卖股票系列

121. Best Time to Buy and Sell Stock

给你股票的股价的序列，至多买一次，获得的最大利润是多少？

• 求每一个点对应之前元素的最小值，或者每一个点对应之后的最大值

122. Best Time to Buy and Sell Stock II

不限制买卖次数(贪心即可)

132. Palindrome Partitioning II

cut划分字符串，是的每一块都是palindrome，求最小cut数？

• 判断回文串 isPalin[n][n]
  • 解法1 类似DP的思路
    • isPalin[i][j] = (s[i] == s[j]) and ((j-i) < = 2)) or isPalin[i+1][j-1]))
  • 解法2 中心点扩张
    • 遍历一遍字符串每次遍历的点当作palindrome的对称点向两端扩展
    • 要分奇数和偶数两种palindrome的情况

• 以i为结尾的最后一个回文串S[j:i+1] => dp[j-1] + 1

  class Solution(object):
    def minCut(self, s):
        n = len(s)
        isPalin = [[False] * n for _ in xrange(n)]
        dp = range(n)
  
        for i in xrange(n):
            isPalin[i][i] = True
            for j in xrange(i+1):
                if s[i] == s[j] and (i-j <= 2 or isPalin[j+1][i-1]):
                    isPalin[j][i] = True
                    dp[i] = min(dp[i], dp[j-1]+1) if j > 0 else 0
        return dp[-1]
  

LintCode 437. Copy Books

其实就是给个Array，要求分成至多k段，求每一段的最大值最小时的值？

• 状态：dp[k][i]表示k个抄写员最少需要多少时间抄完前i本书

Maximum Product of Cut Rope