样例

输入: [1, 2, 2]

输出: true

解释: 先手玩家直接拿走两颗硬币即可.

输入: [1, 2, 4]

输出: false

解释: 无论先手拿一个还是两个, 后手可以拿完, 然后总价值更高.

f[i] = max(

    sum[i+1] - f[i+1] + values[i],                  // 先手者拿一枚

    sum[i+2] - f[i+2] + values[i] + values[i+1]	    // 先手者拿两枚

);

class Solution:

    # @param values: a list of integers

    # @return: a boolean which equals to True if the first player will win

    def firstWillWin(self, values):

        # write your code here

        n, total = len(values), sum(values)

        sumv, f = [], []

        if n<3:

            return True

        # prefix sum

        for i in range(n):

            sumv.append(total)

            total -= values[i]

        f.append(sumv[n-1])

        f.append(sumv[n-2])

        for i in range(n-3, -1, -1):

            f.append(max(values[i]+(sumv[i+1]-f[n-1-i-1]), values[i]+values[i+1]+(sumv[i+2]-f[n-1-i-2])))

        if f[n-1] < sumv[0]-f[n-1]:

            return False

        else: return True

class TrieNode:

    def __init__(self):

        # Initialize your data structure here.

        self.children = [None for i in range(26)]

        self.hasWord = False

        self.str = None

    @classmethod

    def addWord(cls, root, word):

        node = root

        for letter in word:

            child = node.children[ord(letter) - ord('a')]

            if child is None:

                child = TrieNode()

                node.children[ord(letter) - ord('a')] = child

            node = child

        node.hasWord = True

        node.str = word

class Solution:

    # @param {string[]} words a set of strings

    # @param {string} target a target string

    # @param {int} k an integer

    # @return {string[]} output all the stirngs that meet the requirements

    def kDistance(self, words, target, k):

        # Write your code here

        root = TrieNode()

        for word in words:

            TrieNode.addWord(root, word)

        result = []

        n = len(target)

        dp = [i for i in range(n + 1)]

        self.find(root, result, k, target, dp)

        return result

    def find(self, node, result, k, target, dp):

        n = len(target)

        if node.hasWord and dp[n] <= k:

            result.append(node.str)

        next = [0 for i in range(n + 1)]

        for i in range(26):

            if node.children[i] is not None:

                next[0] = dp[0] + 1

                for j in range(1, n + 1):

                    if ord(target[j - 1]) - ord('a') == i:

                        next[j] = min(dp[j - 1], min(next[j - 1] + 1, dp[j] + 1))

                    else:

                        next[j] = min(dp[j - 1] + 1, min(next[j - 1] + 1, dp[j] + 1))

                self.find(node.children[i], result, k, target, next)

样例

样例 1:

	输入:  [3,4,8,5], backpack size=10

	输出:  9

样例 2:

	输入:  [2,3,5,7], backpack size=12

	输出:  12

挑战

注意事项

class Solution:

    """

    @param m: An integer m denotes the size of a backpack

    @param A: Given n items with size A[i]

    @return: The maximum size

    """

    def backPack(self, m, A):

        # write your code here

        # f[i][j]表示前i个物品选一些物品放入容量为j的背包中能否放满。

        n = len(A)

        f = [[False] * (m + 1) for _ in range(n + 1)]

        f[0][0] = True

        for i in range(1, n + 1):

            f[i][0] = True

            for j in range(1, m + 1):

                if j >= A[i - 1]:

                    f[i][j] = f[i - 1][j] or f[i - 1][j - A[i - 1]]

                else:

                    f[i][j] = f[i - 1][j]

        for i in range(m, -1, -1):

            if f[n][i]:

                return i

        return 0

样例

输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]

输出: 9

解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9

输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]

输出: 10

解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

挑战

注意事项

class Solution:

    # @param {int[]} A an integer array

    # @param {int[]} V an integer array

    # @param {int} m an integer

    # @return {int} an array

    def backPackIII(self, A, V, m):

        # Write your code here

        f = [0 for i in range(m+1)]

        for (a, v) in zip(A, V):

            for j in range(a, m+1):

                if f[j - a] + v > f[j]:

                    f[j] = f[j - a] + v

        return f[m]