动态规划

返回首页

返回算法分类分析

第一题 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle

解法

广搜，但是会超时。

class Solution(object):

def __init__(self):
        self.minSum = 999999
        self.depth = 0
        self.tri = []

def cal(self, prevDepth, prevSum, prevPos):
    if prevDepth + 1 == self.depth:
        self.minSum = min(prevSum + self.tri[prevDepth][prevPos], prevSum + self.tri[prevDepth][prevPos+1], self.minSum)
    else:
        self.cal(prevDepth + 1, prevSum + self.tri[prevDepth][prevPos], prevPos)
        self.cal(prevDepth + 1, prevSum + self.tri[prevDepth][prevPos + 1], prevPos + 1)



def minimumTotal(self, triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    d = len(triangle)
    self.depth = d
    self.tri = triangle
    if self.depth == 1:
        return triangle[0][0]
    self.cal(1, triangle[0][0], 0)
    return self.minSum

动态规划

class Solution(object):


def minimumTotal(self, triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    d = len(triangle)
    result = [triangle[0]]
    for i in range(1,d):
        result.append([])
        for j, y in enumerate(triangle[i]):
            if j == 0:
                result[i].append(y + result[i-1][0])
            elif j == len(triangle[i]) - 1:
                result[i].append(y + result[i-1][j-1])
            else:
                result[i].append(min(y+result[i-1][j-1], y+result[i-1][j]))
    return min(result[d-1])

第二题 Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解法

方法值得记下来

class Solution(object):

def subsets(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    result = [[]]
    for i in nums:
        tmp = []
        for j in result:
            tmp.append(j + [i])
        result = result + tmp
    return result

第三题 Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

解法

class Solution(object):

def subsets(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    nums.sort()
    res = {()}
    for num in nums:
        res |= {r + (num,) for r in res}
    return list(res)

第四题 Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

解法

注意这里标记和动态规划的方法。

class Solution(object):
def wordBreak(self, s, wordDict):
    d = {}
    for w in wordDict:
        d[w] = True
    dp = [False for x in range(len(s)+1)]
    dp[0] = True
    for i in range(1, len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in d:
                dp[i] = True
                break
    return dp[-1]

第五题 Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example, Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解法

class Solution(object):
def numTrees(self, n):
    dp = [1, 1] + [0] * (n+1 - 2)
    for i in range(2, n+1): # fill in the dp table
        for j in range(1, i+1): # calc the actual data, loop j from 1 to n as root
            dp[i] += dp[j-1] * dp[i-j]
    return dp[-1]

第六题 Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

解法

class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
    """
    :type obstacleGrid: List[List[int]]
    :rtype: int
    """
    row, col = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * col] * row
    for i in range(row):
        for j in range(col):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i == 0:
                    if j == 0:
                        if obstacleGrid[0][0] == 1:
                            dp[i][j] = 0
                            pass
                        else:
                            dp[i][j] = 1
                            pass
                    else:
                        dp[i][j] = dp[i][j-1]
                    pass
                elif j == 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[row-1][col-1]

第七题 Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

解法

class Solution(object):
def isScramble(self, s1, s2):
    """
    :type s1: str
    :type s2: str
    :rtype: bool
    """
    m = {}
    return self.f(s1, s2, m)

def f(self, s1, s2, m={}):
    if (s1, s2) in m:
        return m[(s1,s2)]
    if len(s1) == 1:
        return s1 == s2
    elif not sorted(s1) == sorted(s2):
        return False
    for i in range(1, len(s1)):
        if self.f(s1[:i], s2[-i:]) and self.f(s1[i:], s2[:-i]) or self.f(s1[:i], s2[:i]) and self.f(s1[i:], s2[i:]):
            m[(s1, s2)] = True
            return True
    m[(s1, s2)] = False
    return False

第八题 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab", Return

[
  ["aa","b"],
  ["a","a","b"]
]

解法

class Solution(object):
def partition(self, s):
    """
    :type s: str
    :rtype: List[List[str]]
    """
    def isPal(s):
        return s == s[::-1]
    n = len(s) + 1
    dp = [[[]]] + [[] for _ in range(n-1)]
    for i in range(1, n):
        for j in range(0, i):
            if isPal(s[j:i]):
                dp[i] += [each+[s[j:i]] for each in dp[j]]
    return dp[-1]

第九题 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.

解法

class Solution(object):
def isInterleave(self, s1, s2, s3, memo={}):
    if len(s1) + len(s2) != len(s3): return False
    if not s1 and not s2 and not s3: return True
    if (s1, s2, s3) in memo:         return memo[s1, s2, s3]
    memo[s1,s2,s3] =\
           (len(s1) > 0 and len(s3) > 0 and s1[0] == s3[0] and self.isInterleave(s1[1:], s2, s3[1:], memo)) or\
           (len(s2) > 0 and len(s3) > 0 and s2[0] == s3[0] and self.isInterleave(s1, s2[1:], s3[1:], memo))
    return memo[s1,s2,s3]

第十题 Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example: S = "rabbbit", T = "rabbit"

Return 3.

解法

class Solution(object):
def numDistinct(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: int
    """
    #注意这里构建数组的方式
    dp = [[0 for j in xrange(0, len(t) + 1)] for i in xrange(0, len(s) + 1)]
    for j in xrange(1, len(t) + 1):
        dp[0][j] = 0
    for i in xrange(1, len(s) + 1):
        dp[i][0] = 1

    dp[0][0] = 1

    for i in xrange(1, len(s) + 1):
        for j in xrange(1, len(t) + 1):
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * (s[i - 1] == t[j - 1])

    return dp[-1][-1]

第十一题 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

解法

class Solution:
# @param s, a string
# @return an integer
def numDecodings(self, s):
    #dp[i] = dp[i-1] if s[i] != "0"
    #       +dp[i-2] if "09" < s[i-1:i+1] < "27"
    if s == "": return 0
    dp = [0 for x in range(len(s)+1)]
    dp[0] = 1
    for i in range(1, len(s)+1):
        if s[i-1] != "0":
            dp[i] += dp[i-1]
        if i != 1 and s[i-2:i] < "27" and s[i-2:i] > "09":  #"01"ways = 0
            dp[i] += dp[i-2]
    return dp[len(s)]

第十二题 Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

解法

class Solution(object):
def grayCode(self, n):
    dp = [[0]]
    for i in range(1,n+1):
        dp.append(dp[i-1] + [2**(i-1) + j for j in dp[i-1]][::-1])
    return dp[n]

第十三题 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

解法

class Solution(object):
def minPathSum(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    row, col = len(grid), len(grid[0])
    dp = [[0 for i in range(col)] for j in range(row)]
    for i in range(row):
        for j in range(col):
            if i == 0 and j == 0:
                dp[i][j] = grid[i][j]
            elif i == 0:
                dp[i][j] = dp[i][j-1] + grid[i][j]
            elif j == 0:
                dp[i][j] = dp[i-1][j] + grid[i][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[-1][-1]