买卖股票问题与动态规划

买卖股票问题与动态规划

贪心

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

给定起点，每步可以走的步数为A[i],判断能不能走到最后一个

用贪心策略，刚开始 step = A[0]，到下一步 step–, 并且取 step = max(step, A[i])，这样 step 一直是保持最大的能移动步数，局部最优也是全局最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 0:
            return True
        step = nums[0]
        for i in range(1,len(nums)):
            if step > 0:
                step = step -1
                step = max(step, nums[i])
            else:
                return False
        return True

45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

You can assume that you can always reach the last index.

step: 目前为止的 jump 数

curReach: 从 A[0] 进行 step 次 jump 之后达到的最大范围

maxReach: 从 0~i 这 i+1 个 A 元素中能达到的最大范围

当 curReach < i，说明 step 次 jump 已经不足以覆盖当前第 i 个元素，因此需要增加一次 jump，使之达到记录的 maxReach。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        step = 0
        curReach = 0
        maxReach = 0
        for i in range(len(nums)):
            if curReach < i:
                step += 1
                curReach = maxReach
            maxReach = max(maxReach, nums[i] + i)
        return step

动态规划

Best Time to Buy and Sell Stock I

tag:dp

Say you have an array for which the i th element is the price of a given stock on day i .

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

给一个数 prices[]，prices[i] 代表股票在第 i 天的售价，求出只做一次交易 (一次买入和卖出) 能得到的最大收益。

只需要找出最大的差值即可，即 max(prices[j] – prices[i]) ，i < j。一次遍历即可，在遍历的时间用遍历 low 记录 prices[o….i] 中的最小值，就是当前为止的最低售价，时间复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        
        if len(prices) == 0:
            return 0
        low = prices[0]
        ans = 0
        for i in range(len(prices)):
            if prices[i] < low:
                low = prices[i]
            if ans < prices[i] - low:
                ans = prices[i] - low
        return ans

122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)

此题和上面一题的不同之处在于不限制交易次数。也是一次遍历即可，只要可以赚就做交易。

tag: greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        ans = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i - 1]:
                ans += prices[i] - prices[i - 1]
        return ans

123. Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

tag:dp

买卖两次

此题是限制在两次交易内，相对要难一些。容易想到的解决办法是，把 prices[] 分成两部分 prices[0…m] 和 prices[m…length] ，分别计算在这两部分内做交易的做大收益。由于要做 n 次划分，每次划分可以采用 第一题： Sell Stock I 的解法， 总的时间复杂度为 O(n^2).

但是由于效率过低，运行超时。可以利用动态规划的思想进行改进，保持计算的中间结果，减少重复的计算。

那就是第一步扫描，先计算出子序列 [0,…,i] 中的最大利润，用一个数组保存下来，那么时间是 O(n)。计算方法也是利用第一个问题的计算方法。 第二步是逆向扫描，计算子序列 [i,…,n-1] 上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是 O(n)。 所以最后算法的复杂度就是 O(n) 的。

就是说，通过预处理，把上面的函数的复杂度降到 O(1)

动态规划法。以第 i 天为分界线，计算第 i 天之前进行一次交易的最大收益 preProfit[i]，和第 i 天之后进行一次交易的最大收益 postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1) 就是最大收益。第 i 天之前和第 i 天之后进行一次的最大收益求法同 Best Time to Buy and Sell Stock I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n <= 1:
            return 0
        p1 = [0] * n
        p2 = [0] * n
        #正向遍历
        minV = prices[0]
        for i in range(1, n):
            minV = min(prices[i], minV)
            p1[i] = max(p1[i - 1], prices[i] - minV)
        
        #反向遍历
        maxV = prices[-1]
        for i in range(n-2, -1, -1):
            maxV = max(prices[i], maxV)
            p2[i] = max(maxV - prices[i], p2[i + 1])
            
        res = 0
        for i in range(n):
            res = max(p1[i] + p2[i], res)
        return res

123. Best Time to Buy and Sell Stock III

参见参考链接

参考链接1
参考链接2

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

状态转移方程：

dp[x + c] = min(dp[x] + 1, dp[x + c])

其中 dp[x] 代表凑齐金额 x 所需的最少硬币数，c 为可用的硬币面值

初始令 dp[0] = 0

贪心算法是不正确的，因为有可能会错过全局最优解。

举个例子，如果 amount = 8, coins 为[1, 3, 5, 6]，我们会发现，采用贪心策略得到3（6，1，1），而实际正确值为2（5，3），之所以贪心法在这里不适用是因为贪心所作的决策并不能确保全局的最优，如果换作这样的问题，提水，每桶都有一定量的水，怎样才能最少次数运完所有的水，这样肯定就是贪心选择最多的水。因为每次提越多的水，最后的次数肯定最少

问题可以转化为求 X 轴 0 点到坐标点 amount 的最短距离（每次向前行进的合法距离为 coin 的面值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [0] + [-1] * amount
        for x in range(amount):
            if dp[x] < 0:
                continue
            for c in coins:
                if x + c > amount:
                    continue
                elif dp[x + c] < 0:
                    dp[x + c] = dp[x] + 1
                else:
                    dp[x + c]  = min(dp[x] + 1, dp[x + c])
        return dp[amount]

416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:

1
2
3
4
5
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
4
5
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s % 2 == 1:
            return False
        return self.canFindSum(nums, s/2, 0, len(nums), {})
    def canFindSum(self, nums, target, start, end, d):
        if target in d:
            return d[target]
        if target == 0:
            d[target] = True
        else:
            d[target] = False
            for i in range(start, end):
                if self.canFindSum(nums, target - nums[i], i + 1, end, d):
                    d[target] = True
                    break
        return d[target]

Minimax

486. Predict the Winner

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

1
2
3
4
5
6
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

Example 2:

1
2
3
4
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

参考链接
参考链接2

So assuming the sum of the array it SUM, so eventually player1 and player2 will split the SUM between themselves. For player1 to win, he/she has to get more than what player2 gets. If we think from the prospective of one player, then what he/she gains each time is a plus, while, what the other player gains each time is a minus. Eventually if player1 can have a >0 total, player1 can win.

大意就是说，两个人将整个数组的和分割成两半，如果1想赢，要比2拿到的更多才行。1拿到的都加，2拿到的都减。

1
2
3
4
5
6
7
8
public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return helper(nums, 0, nums.length-1)>=0;
    }
    private int helper(int[] nums, int s, int e){        
        return s==e ? nums[e] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e));
    }
}

这个是比较1拿到的和2拿到的哪个多

l,如果1拿到了左的话的总数

r,如果1拿到了右的话的总数

用记忆话搜索保留边界为l,r的时候，1拿到的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def check(left, right, memo):
            if left > right:
                return 0
            if left == right:
                return nums[left]
            if not (left, right) in memo:
                ss = sum(nums[left:right + 1])
                l, r = ss - check(left + 1, right, memo) + nums[left], ss - check(left, right - 1, memo) + nums[right]
                memo[(left, right)] = max(l, r)
            return memo[(left, right)]
            
        s = sum(nums)
        c1 = check(0, len(nums) - 1, {})
        return c1 >= s - c1

464. Can I Win

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

题目大意：
在 “100 游戏” 中，两个玩家轮流从整数 1-10 中取数相加，得到一个累加值。第一个使累加值达到或者超过 100 的玩家获胜。

我们修改游戏规则，用过的数字不能重复使用，会怎样呢？

例如，两个玩家可以轮流从 1..15 中无放回的取数字，使得累加值 >=100。

给定整数 maxChoosableInteger 和 desiredTotal，判断第一个玩家是否一定能赢，假设两名玩家都采用最优策略。

你可以总是假设 maxChoosableInteger 不大于 20，desiredTotal 不大于 300。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
            return False
        self.memo = {}
        return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)
        
    def helper(self, nums, desiredTotal):
        hash = str(nums)
        if hash in self.memo:
            return self.memo[hash]
        if nums[-1] >= desiredTotal:
            return True
        for i in range(len(nums)):
            # The second player's state is described by the next line, and the conclusion of which is used to determine the state of the first player
            if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
                self.memo[hash] = True
                return True
        
        self.memo[hash] = False
        return False

375. Guess Number Higher or Lower II

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

1
2
3
4
5
6
7
8
9
n = 10, I pick 8.
First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.
Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.

区间动归

dp[i][j] = min(k + max(dp[i][k - 1], dp[k + 1][j]))

参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        dp = [[0] * (n+1) for _ in range(n+1)]
        for x in range(1, n):
            for i in range(1, n+1-x):
                j = i + x
                minNum = sys.maxint
                for k in range(i, j):
                    dp[i][j] = k + max(dp[i][k - 1], dp[k + 1][j])
                    minNum = min(minNum, dp[i][j])
                    dp[i][j] = minNum
        return dp[1][n]

回溯

算法
算法