Given an array of n non-negative numbers, the task is to find the minimum sum of elements (picked from the array) such that at least one element is picked out of every 3 consecutive elements in the array.


In [38]:
def findMinSum(arr, n):
    
    # Create a DP table to store results of
    # subpriblems. sum[i] is going to store
    # minimum possible sum when arr[i] is
    # part of the solution.
    sumN = [0]*n
 
    # When there are less than or equal to
    # 3 elements
    sumN[0] = arr[0]
    sumN[1] = arr[1]
    sumN[2] = arr[2]
 
    # Iterate through all other elements
    for i in range(3,n):
        sumN[i] = arr[i] +min(sumN[i-3], sumN[i-2], sumN[i-1]);
 
    return min(sumN[n-1], sumN[n-2], sumN[n-3])

def findMinSumR(arr, offset):
    
    minN = sys.maxint
    for (int i = 0; i < offset; i++):
        minN = Integer.min(findMin(arr, i, offset), min)
    
    return minN

def findMin(arr, i, offset):

        if (i >= arr.length)
            return 0

        int sum = sys.maxint
        for (int in = i + 1; in <= i + offset; in++) {
            sum = Integer.min(arr[i] + findMin(arr, in, offset), sum);
        }

        return sum;

In [42]:
arr = [1, 2, 3, 20, 2, 10, 1]
#arr = [1, 2, 3, 6, 7, 1, 8, 6, 2, 7, 7, 1]

In [62]:
import re
s = '   a   b '

string = re.split("[' ']+", s.strip())
string.reverse()
s = " ".join(string) 
print s


b a

Cost of running a business (difficulty: 5)

You are running a small business for n months. Each month i, you either run it out of your office in New York and incur an operating cost Ni, or out of your office in Seattle and incur a cost Si. If you move to a different city in month i + 1, you pay a fixed cost M.
A plan is a sequence of n locations such that the i-th location indicates the city you will based in month i. The cost of a plan is the sum of all the operating costs plus any moving costs. Give an algorithm that computes the plan of minimum cost, and its cost.
Example: n = 4, M = 10, Ni,Si as below


In [15]:
n = 4
M = 10
NY = [1, 3, 20, 30]
SE = [50, 20, 2, 4]

NY = [100, 1, 100, 1, 100, 1, 100, 1, 100, 1] 
SE = [1, 100, 1, 100, 1, 100, 1, 100, 1, 100]
n = 10
M = 10

dp = [0]*n
dp[0] = 'NY' if NY[0] < SE[0] else 'SE'

for i in range(1, n):

    if dp[i-1] == 'NY':
        dp[i] = 'NY' if NY[i] + M < SE[i] else 'SE'
    else:
        dp[i] = 'NY' if NY[i] < SE[i] + M else 'SE'

print dp


['SE', 'NY', 'SE', 'NY', 'SE', 'NY', 'SE', 'NY', 'SE', 'NY']

Travel Planning (difficulty: 5)

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < · · · < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. Your destination is the final hotel (at distance an) and you must stop there.
You’d ideally like to travel 200 miles a day, but this may not be possible, depending on the spacing of the hotels. If you travel x miles during a day, the penalty for that day is (200 − x)2. Your task is to give an efficient algorithm that minimizes the total penalty —that is, the sum, over all travel days, of the daily penalties.


In [27]:
a = [0]
opt = [0]

a = [0,200]
opt = [0, 0]

a = [0,200,400,600,800,1000]
opt = [0, 0, 0, 0, 0, 0]

a = [0,400,800,1600,1700,112000]
opt = [0, 40000, 80000, 440000, 450000, 12122460000]

a = [0,100,150,300,350,550,750,800,950]
opt = [0, 10000, 2500, 5000, 2500, 2500, 2500, 5000, 2500]

n = len(a)
dp = [0]*n

for i in range(1, n):
    dp[i] = sys.maxint
    for j in range(i):
        tmp = dp[j] + (200 - (a[i] - a[j]))**2

        if tmp < dp[i]:
            dp[i] = tmp
            
print dp


[0, 10000, 2500, 5000, 2500, 2500, 2500, 5000, 2500]

A game with stones (difficulty: 5)

You’re playing a game with stones. At the beginning of the game, there are n piles of stones, each of size pi ≥ 1, in a line. Your goal is to merge the stones in one big pile subject to the following rules of the game:

  1. At each step, you can merge two adjacent piles of sizes x, y to obtain a new pile of size x+y.
  2. The cost of merging a pile of size x with a pile of size y is x+y.

Your goal is to merge all the stones in one big pile so that the total cost is minimized. Design an algorithm for this task.


In [ ]:

Longest monotonically increasing subsequence (dificulty: 5)

Give an e cient algorithm to compute the length of the longest increasing subsequence of a sequence of numbers a1, . . . , an.
A subsequence is any subset of these numbers taken in order, of the form ai1,ai2,...,aik, where 1  i1 < i2 < ... < ik  n. An increasing subsequence is one in which the numbers are getting strictly larger.
Example
Input: 5,2,8,6,3,6,7
Output: 4 (corresponding to subsequence 2, 3, 6, 7)


In [9]:
a = [5,2,8,6,3,6,7]
n = len(a)
dp = [1]*n

for i in range(1,n):
    for j in range(0,i):
        if a[i] > a[j] and dp[i] < dp[j] + 1:
            dp[i] = dp[j]+1
            
print dp


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

A card game (dificulty: 8)

Consider the following game. To begin, n cards are laid out in order from left to right, where n is even. The i-th card from the left has value vi. Two players take turns, each taking one card, with the restriction that on a player’s turn, they can only take either the leftmost or the rightmost card remaining. The goal is to collect cards of the largest total value.
Give an O(n2) dynamic programming algorithm that precomputes the optimal strategy.


In [24]:
def card_game(a):
    
    n = len(a)
    dp = [[0]*n for _ in range(n)]
    
    for gap in range(n):
        for i, j in zip(range(0, n), range(gap, n)):
            x = dp[i+2][j] if (i+2) <= j else 0
            y = dp[i+1][j-1] if (i+1) <= (j-1) else 0            
            z = dp[i+2][j] if i <= (j-2) else 0
            dp[i][j] = max(a[i] + min(x, y), a[j] + min(y, z))            
            
    for i in range(n):
        for j in range(n):
            print dp[i][j],'\t',
        print 
        
    return dp[0][n-1]

a = [8, 15, 3, 7]
card_game(a)


8 	15 	11 	15 	
0 	15 	15 	18 	
0 	0 	3 	7 	
0 	0 	0 	7 	
Out[24]:
15