Algorithm

每日一刷-Burst_Balloon

[每日一刷] (Burst Balloon)


Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.

Example:
Given [3, 1, 5, 8]
Return 167

解题思路


看到maximum coins, 发现是一道求最优解的题，马上想到使用动态规划
本题的最优子结构是opt[i~j] = opt[i~k-1] + score[k] + opt[k+1~j], 其中k指的是最后一个爆破的气球的位置
本题的trick在于在算最优子结构的时候要在两边多算一个位置。例如算opt[1,2]的时候要将0, 3都算进去

代码虽然在leetcode上超时了，不过同样的做法使用JAVA和C++却可以通过，可能还是因为Python太慢了吧-.-

Python:

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
28
29
30
31
32
33
34
35
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n^3)
"""
prices = [1, 2, 3, 0, 2]
class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums.insert(0, 1)
        nums.append(1)
        # table[i][j] stores the optimal result of bursting balloon starts at i and the length is j
        # balloon starts from 1 to n
        table = [[0 for i in xrange(n-I+1)] for I in xrange(n+1)]
        table.insert(0, []) 
        for i in xrange(1, n+1):
            table[i][1] = nums[i-1] * nums[i] * nums[i+1]
        for l in xrange(2, n+1): # length from 2 to n
            for j in xrange(1, n-l+2): # balloon can starts from balloon 1 to balloon n-l+1
                maximum = 0
                for i in xrange(j, j+l): # balloon i is the last burst balloon
                    if i < j+l-1:
                      temp = table[j][i-j] + table[i+1][j+l-i-1] + nums[i]*nums[j-1]*nums[j+l]
                    else:
                      temp = table[j][i-j] + nums[i]*nums[j-1]*nums[j+l]
                    maximum = max(maximum, temp)
                table[j][l] = maximum
        return table[1][n]

Algorithm

每日一题-Best_Time_to_Buy_and_Sell_Stock_with_Cooldown

[每日一题] (Best Time to Buy and Sell Stock with Cooldown)
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) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

解题思路


本题使用动态规划，解题思路类似于抢劫问题。使用3个变量free, cool, have来存储当前位置的最优解。
free用来存储到当前位置，状态为空闲时的最优解
have用来存储到当前位置，状态为持有股票时的最优解
cool用来存储到当前位置，状态为正在冷却时的最优解

状态转移矩阵为：
free = max(free, cool) # 当前free的最优解由上一时间free的最优解和cool的最优解得出
have = max(have, free-p) # 当前have的最优解由上一时间持有股票时的最优解和上一时间空闲而这一时间购买股票的最优解得出
cool = have + p #当前cool的最优解由上一时间持有股票的最优解再在这一时间卖出得出

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/env 
# -*- coding:utf-8 -*-
"""
时间复杂度 O(n)
"""
prices = [1, 2, 3, 0, 2]
class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    free = 0
    have = cool = float('-inf')
    for p in prices:
        free, have, cool = max(free, cool), max(have, free-p), have+p
    return max(free, cool)