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
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
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
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:
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 [ ]:
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
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)
Out[24]: