Coding Questions - Dynamic Programming

General DP solution steps: 1. Think in a divide and conquer way 2. Each sub-step should have overlap between each other 3. Build an eqaution between current step’s optimum solution and prev’s solution

solution have optimal substructure and overlapped subproblems

  1. Wild Card Match
    *. Recursive Thinking

    Base Case ? Case * Case which needs to build solution recursively

    *. Once you have Recursive Solution, you can either

    Use memoization to improve time complexity Use DP to imporove time complexity

    *. T(n) = T(n-1) + T(n-2) –> O(2**n)

    We can reduce the time complexity to polynomial time O(mn)!

  2. Frog Jump

    Same as above solution, you can build recursive solution first!

  3. Unique Ways

    *. DP: Build one DP and find the relationship between last step and last-1 step *. Combination: There’re M+N steps, and we know we will get to the final states, as long as we perform M right move and N down move.

    Then we can use combination to solve the problem.

  4. House Robber
    Solution::

    # Recursive class Solution(object):

    def rob(self, nums):

    “”” :type nums: List[int] :rtype: int “”” self.money = 0

    def helper(idx, nums, curr, robbed):
    if idx == len(nums):

    self.money = max(self.money, curr) return

    if not robbed:

    helper(idx+1, nums, curr+nums[idx], True) helper(idx+1, nums, curr, False)

    else:

    helper(idx+1, nums, curr, False)

    helper(0, nums, 0, True) helper(0, nums, 0, False) return self.money

    # DP def rob(self, nums):

    “”” :type nums: List[int] :rtype: int “”” dp = [0]*(len(nums)+1) for i in range(1, len(nums)+1):

    dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

    return dp[-1]

    Robber II:

    max(rob_line(nums[:-1]), rob_line(nums[1:]))

  5. Win or Lose

  6. Longest Subsequence

    *. Find the recursive structure first *. Convert it into dynamic programming paradigm

  7. Panlindromic string

    When it comes to panlindromic string, think in a recursive way, you can check it layer by layer. And when build the DP solution, inner loop is from bottom to the top because of DP[i+1][j-1]

  8. Buy and Sell Stocks

    *. If you get a diff array, that’s maxium sub-array problem which can be solved in DP or Divide and Conquer *. We can build a 2 Dimensional DP, trick is we don’t know how’s 1st transaction like thus we need to have additional for loop to check this:

    # This is also a great example to reduce time complexity.
class Solution(object):
    def maxProfit(self, prices):
        k = 2 # at most 2 transactions
        dp = [[0]*(len(prices)+1) for _ in range(k+1)]

        for i in range(1, k+1):
            for j in range(1, len(prices)+1):
                tmpProfit = 0
                for pos in range(1, j):
                    tmpProfit = max(tmpProfit, prices[j-1]-prices[pos-1]+dp[i-1][pos])
                dp[i][j] = max(dp[i][j-1], tmpProfit)
        return dp[-1][-1]

  9. Maximum subarray problem

  10. Knapsack problem

  11. Build Stairs

  12. Fibonacci

LeetCode 691. Stickers to Spell Word

  • First thought should be how to solve it using navie method
  • 2nd thought should be able to find some recusion pattern
  • 3rd thought should be able to come up with DP optimization

solution:

#hello world

Knapsack problem - 0/1 Knapsack

You are the owner of a local store and you have a budget of N to spend on purchasing goods, different suppliers have different bundle options with different prices. You can buy only one bundle from each supplier untill the budget is used off. What’s your max units you can get using N budget?

This is 0/1 knapsack because you either choose or not.

  • 可以利用一维的**滚动**数组模拟二维数据

    另外由于这里由i−1的前面的解j−c[i]推导出i后面的解j，也就是利用一维的数据的话，旧解为前面的解，新解为后面的． 那么就应该让j从大到小进行循环遍历，因为这样第一次接触的到为旧解i−1，新出来的新解j在此次遍历也不会再用到．

  • 另一个小的常数时间优化

    在利用dfs递归求解时，先将物品按照单位价格排好序，单位价格高的靠前，这样如果某个物品超载时，没必要再累积其后面物品的价格， 而是按照该物品的单位价格乘以剩余容量，这样算出的总价格虽然比实际装载的总价格略高些，如果这样略高于实际值的解还低于当前的最优解，则可对后面剪枝，避免多余的计算．

http://www.hawstein.com/posts/dp-knapsack.html http://blog.csdn.net/u010106759/article/details/77984537

Solution and Explaination:

class Solution(object):
    def knapsack(self, n, bundles, costs):
        # this is a 0/1 knapsack problem, we can only choose True/False once for each position.
        # dp[i][j] means the max bundles when we have i choices with j costs.
        dp = [[0]*(n+1) for _ in range(len(bundles)+1)]

        for i in range(1, len(bundles)+1):
            for j in range(1, n+1):
                if j >= costs[i-1]:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-costs[i-1]]+bundles[i-1])
        print dp
        return dp[-1][-1]

    # although we can compress the space complexity but the time complexity keeps the same
    # therefore we still have 2 loops.
    def knapsack_1(self, n, bundles, costs):
        # dp[j] means the max bundles when we have i choices with j costs.
        dp = [0]*(n+1)

        for i in range(1, len(bundles)+1):
            # each time when we have dp, it keeps last states which is i-1
            # Since we have dp[j-costs[i-1]] part, i-1 status will be lost if we update it first,
            # we need to do it from the end to the front.
            for j in range(n, -1, -1):
                if j >= costs[i-1]:
                    dp[j] = max(dp[j], dp[j-costs[i-1]]+bundles[i-1])
        return dp[-1]

def beautiful_print(data):
    if type(data) is list and type(data[0]):
        for value in data:
            print value

print Solution().knapsack_1(38, [3, 5, 4], [10, 20, 16])


# Below solution is wrong because i didn't consider the ordering!
def knapsack_new(self, n, bundles, costs):
    dp =[(0, 0) for i in range(len(bundles)+1)]

    for i in range(1, len(bundles)+1):
        if n-dp[i-1][1] >= costs[i-1]:
            dp[i] = (dp[i-1][0]+bundles[i-1], dp[i-1][1]+costs[i-1]) if dp[i-1][0]+bundles[i-1] > dp[i-1][0] else dp[i-1]
        else:
            dp[i] = dp[i-1]
    return dp[-1][0]

Knapsack problem - Unbounded Knapsack

You are the owner of a local store and you have a budget of N to spend on purchasing goods. Different suppliers have different bundle options with different prices. You can buy as many as bundles from each supplier untill the budget is used off. What’s your max units you can get using N budget?

Notation:
Budget : N = 50
BundleUnits : B = [5, 15, 20]
BundlePrice : P = [5, 10, 15]
MaxUnit : t = (50/10)*15=75

Thoughts:

0/1背包只考虑放与不放进去两种情况，而完全背包要考虑 放0,放1, ···, 放j/w[i] 的情况.

The unbonded problem can be converted to 0/1 knapsack problem:

for i in range(1, len(bundles)+1):
    for j in range(n, -1, -1):
        tmp = 0
        for k in range(1, j/costs[i-1]+1):
            tmp = max(tmp, dp[i-1][j-k*costs[i-1]] + bundles[i-1]*k)
        dp[i][j] = max(tmp, dp[i-1][j])

Above solution’s time complexity is O(N*len(B)*sum(k)) which is a little high.

  • A simple optimiazation is to add one more check: if costs[i] < costs[i+1] and bundles[i]>bundles[i+1], then we can skip i+1 case.

  • Another optimiazation is to divide last item to 0/1 problem using 2 as the base, then the loop goes to O(log(k)) instead of k.

    这是二进制的思想. 因为, 不管最优策略选几件第 i 种物品, 其件数写成二进制后, 总可以表示成若干个 2^k 件物品的和.

In fact, this problem can be coverted to O(N*len(B)), the only difference is:

dp[i][j] = max(dp[i-1][j], dp[i][j-costs[i-1]]+bundles[i-1])

Instead of dp[i-1], dp[i] will contain all the possible solutions at i-1 (i’m still confused about this form and haven’t found a good way to explain)

Try to understand this, i think it makes sense:
dp[i][j-1]+v[i]代表至少放了一个第i种物品, 当然它的前提是能放进去（j>=w[i]）, 所以dp[i][j]=max{dp[i-1][j],dp[i][j-w[i] ]+v[i]}已经涵盖了一个都不放与至少放一个第i种物品的情况了.

http://blog.csdn.net/qq379666774/article/details/17581377

LeetCode 121. Best Time to Buy and Sell Stock

If you were only permitted to complete at most one transaction::

# you can get max profix using one transaction in O(n) class Solution(object):

def maxProfit(self, prices):

buy = float(‘inf’) sell = 0 for i in range(len(prices)):

buy = min(buy, prices[i]) sell = max(sell, prices[i]-buy)

return sell

LeetCode 122. Best Time to Buy and Sell Stock II

You may complete as many transactions as you like:

class Solution(object):
    def maxProfit(self, prices):
        # the idea is to capture every profit.
        # you can sell and buy immediately at the same day
        profit = 0
        for i in range(1, len(prices)):
            if prices[i]>prices[i-1]:
                profit += prices[i]-prices[i-1]

        return profit

LeetCode 123. Best Time to Buy and Sell Stock III and IV

This is a standard DP solution, i think the hardest part to come up with the DP helper array,

DP[i][j] means the profit you have at j with i transactions

The state function is simple and you need to use the temp variable to reduce complexity:

class Solution(object):
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0
        # the 3rd inner loop to check each position and find max profit is unnecessary
        # we can try to use a tmp variable to reduce the time complexity
        k = 2
        if len(prices) < 2:
    return 0
        # k is big enougth to cover all ramps.
        if k >= len(prices) / 2:
            return sum(i - j for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
        dp = [[0] * (len(prices) + 1) for _ in range(k + 1)] # this means the max profit with k transctions.
        for i in range(1, k+1):
            # initial
            tmpMaxProfit = dp[i - 1][0] - prices[0] # use this varaible to get the profit at each transctions
            for j in range(1, len(prices)+1):
                # dp[i][j]  1> dp[i][j-1]
                #           2> for m in range(j-1]:
                #                   prices[j-1] + dp[i-1][m] - prices[m]
                # Explaination: 1> we used up all transactions before last stock
                                2> we leave the last transaction to j-1, we need to find the max profit we can make within (1, j-1]

                # Since we are already checking all positions and 2> can be transformed to prices[j-1] + {dp[i-1] - prices[m]} for m in range(1, j)
                # Then we can reduce the for loop to one variable.

                # Trick is, the prev buy choice could be any price before j-1, thus you have to check or find the max local
                # and that would be your new value, then use tmpMaxProfit
                # tmpMaxProfit = dp[i-1][j] - prices[j-1]: use one variable to reduce the loop
                dp[i][j] = max(dp[i][j - 1],  tmpMaxProfit + prices[j-1])
                tmpMaxProfit = max(tmpMaxProfit, dp[i - 1][j] - prices[j-1]) # initial for next level
        return dp[-1][-1]

LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

Don’t worry, you can try to use the Brute Force to solve it first:

class Solution(object):
    def maxProfit(self, prices):
        # Solution 1:
        # enumerate all the possible solutions and check for the max value
        # Each position has 3 ways to do: O(3**n)

        # Solution 2:
        # Record max PROFIT value for each state
        # hold[i] = max(hold[i-1], res[i-1]-prices[i]) - hold previous or buy current
        # sold[i] = hold[i-1] + prices[i] - sell current
        # rest[i] = max(res[i-1], sold[i-1])
        # return max(sold[i], rest[i])
        sold = 0
        rest = 0
        hold = float('-inf')
        for price in prices:
            prev = sold
            hold = max(hold, rest-price)
            sold = hold + price
            rest = max(rest, prev)
        return max(rest, sold)
        # Solution 3:
        # Record max PROFIT value for each state
        # sell[i] - PROFIT when sell at day i
        # cooldown[i] - PROFIT when day i is cooldown
        if not prices or len(prices)<2:
            return 0

        n = len(prices)
        sell = [0]*n
        cool = [0]*n
        sell[1] = prices[1]-prices[0]
        for i in range(2, n):
            cool[i] = max(sell[i-1], cool[i-1])
            sell[i] = prices[i] - prices[i-1] + max(sell[i-1], cool[i-2])
        return max(sell[-1], cool[-1])

LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee

Solution:

class Solution(object):
    def maxProfit(self, prices, fee):
        # Solution 1:
        # enumerate all the possible solutions and check for the max value
        # Each position has 2 ways to do: O(2**n)

        # Solution 2:
        # Similar to with cooldown problem, we can use 2 arrays to record the state.
        # buy[i] - PROFIT when we buy at day i BUY or NOT
        # sell[i] - PROFIT when we sell at day i SELL or NOT

        buy = [0] * len(prices)
        sell = [0] * len(prices)

        buy[0] = - prices[0]
        sell[0] = 0

        for i in range(1, len(prices)):
            buy[i] = max(sell[i-1]-prices[i], buy[i-1]) # you have to sell before buy
            sell[i] = max(buy[i-1]+prices[i]-fee, sell[i-1])
        return sell[-1]

Leetcode 53. Maximum Subarray

This is a very basic problem which can be used to help you understand the following concepts:
# Divide and Conquer # DP solution # DP solution with minimum space complexity

DP Solution:

dp = [0]*(len(nums)+1)
for i in range(1, len(nums)+1):
    dp[i] = max(dp[i-1], dp[i-1]+nums[i-1])
return dp[-1]

This is my initial thought, however, this equation doesn’t meet the requirement of continous subarray. Keeping the condition in mind then we can reformat the condition a little bit:

DP[i] means the maximum subarray that ends at position i

The code should look like this:

def maxSubArray(self, nums):
    dp = [float('-inf')]*(len(nums)+1)
    for i in range(1, len(nums)+1):
        dp[i] = max(nums[i-1], dp[i-1]+nums[i-1])
    return max(dp)

If you want to reduce the space complexity, you can replace the DP array with 2 variables. Optimized DP solution:

def maxSubArray(self, nums):
    maxEnding = float('-inf')
    globalMax = float('-inf')
    for i in range(len(nums)):
        maxEnding = max(nums[i], maxEnding+nums[i])
        globalMax = max(globalMax, maxEnding)
    return globalMax

https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts https://discuss.leetcode.com/topic/4175/share-my-solutions-both-greedy-and-divide-and-conquer