(Dynamic Programming) Minimum Cost Problem

min_cost_toys.py

import sys
import string
import fileinput

inputs = fileinput.input()
numToys = int(inputs[0].replace('\n', ''))
toys = inputs[1].replace('\n', '')
toys = sorted([int(w) for w in toys.split(' ')])
minus_four = [w - 4 for w in toys]
prev_toys = {}

j = 0
for i in range(0, numToys):
	if toys[j] >= minus_four[i]:
		prev_toys[i] = j - 1
	while toys[j] < minus_four[i]:
		if toys[j+1] >= minus_four[i]:
			prev_toys[i] = j
			break
		j = j + 1

min_point = {
	-1: 0
}

# print toys
# print prev_toys

for i in range(0, numToys):
	prev_toy = prev_toys[i]
	potential_vals = []
	for j in range(prev_toy, i):
		potential_vals.append(1 + min_point[prev_toys[j + 1]])
	min_point[i] = min(potential_vals)

# print min_point

print min_point[numToys-1]


"""
Challenge URL: https://www.hackerrank.com/contests/w12/challenges/priyanka-and-toys
Test cases:
7
1 2 3 7 11 17 15

1
1

6
1 2 3 7 17 10

5
1 2 3 17 10

10
1 2 3 3 4 10 35 36 37 49

7
1 2 3 3 4 10 35


3
1 2 3
"""