```
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

```
```

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’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:

- At each step, you can merge two adjacent piles of sizes x, y to obtain a new pile of size x+y.
- 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 [ ]:
```

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

```
```

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]:
```