Given an array nums[] of size n, where nums[i] denotes the number of characters in one word. Let K be the limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly.
Assume that the length of each word is smaller than the line width. When line breaks are inserted there is a possibility that extra spaces are present in each line. The extra spaces include spaces put at the end of every line except the last one. 
You have to minimize the following total cost where total cost = Sum of cost of all lines, where cost of line is = (Number of extra spaces in the line)^{2}.
Example 1:
Input: nums = {3,2,2,5}, k = 6
Output: 10
Explanation: Given a line can have 6
characters,
Line number 1: From word no. 1 to 1
Line number 2: From word no. 2 to 3
Line number 3: From word no. 4 to 4
So total cost = (6-3)^{2} + (6-2-2-1)^{2} = 3^{2}+1^{2} = 10.
As in the first line word length = 3 thus
extra spaces = 6 - 3 = 3 and in the second line
there are two word of length 2 and there already
1 space between two word thus extra spaces
= 6 - 2 -2 -1 = 1. As mentioned in the problem
description there will be no extra spaces in
the last line. Placing first and second word
in first line and third word on second line
would take a cost of 0^{2} + 4^{2} = 16 (zero spaces
on first line and 6-2 = 4 spaces on second),
which isn't the minimum possible cost.
Example 2:
Input: nums = {3,2,2}, k = 4
Output: 5
Explanation: Given a line can have 4 
characters,
Line number 1: From word no. 1 to 1
Line number 2: From word no. 2 to 2
Line number 3: From word no. 3 to 3
Same explaination as above total cost
= (4 - 3)^{2} + (4 - 2)^{2} = 5.
Your Task:
You don't need to read or print anyhting. Your task is to complete the function solveWordWrap() which takes nums and k as input paramater and returns the minimized total cost.
 
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n)
 
Constraints:
1 ≤ n ≤ 500
1 ≤ nums[i] ≤ 1000
max(nums[i]) ≤ k ≤ 2000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def solveWordWrap(self, nums, k):

		#Code here

Solutions:
class Solution:

	def solveWordWrap(self, nums, k):
		A = nums
		n = len(A)
		dp = [float('inf')] * n
		dp[-1] = 0
		for i in range(n - 2, -1, -1):
			length = -1
			for j in range(i, n):
				length += A[j] + 1
				if length <= k:
					if j == n - 1:
						cost = 0
					else:
						cost = (k - length) ** 2 + dp[j + 1]
				else:
					break
				dp[i] = min(dp[i], cost)
		return dp[0]


class Solution:

	def solveWordWrap(self, arr, k):
		dp = []
		n = len(arr)
		for i in range(n + 1):
			temp = [-1] * (k + 1)
			dp.append(temp)

		def recFunc(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			ans = 0
			if arr[i] > rem:
				ans = (rem + 1) * (rem + 1) + recFunc(i + 1, k - arr[i] - 1)
			else:
				ch1 = (rem + 1) * (rem + 1) + recFunc(i + 1, k - arr[i] - 1)
				ch2 = recFunc(i + 1, rem - arr[i] - 1)
				ans = min(ch1, ch2)
			dp[i][rem] = ans
			return dp[i][rem]
		return recFunc(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		dp = {}

		def rec(i, rem, nums, k):
			if i == len(nums):
				return 0
			if (i, rem) in dp:
				return dp[i, rem]
			if nums[i] > rem:
				ans = (rem + 1) * (rem + 1) + rec(i + 1, k - nums[i] - 1, nums, k)
			else:
				choice1 = (rem + 1) * (rem + 1) + rec(i + 1, k - nums[i] - 1, nums, k)
				choice2 = rec(i + 1, rem - nums[i] - 1, nums, k)
				ans = min(choice1, choice2)
			dp[i, rem] = ans
			return dp[i, rem]
		return rec(0, k, nums, k)


class Solution:

	def solve(self, i, n, nums, k, dp):
		if i == n - 1:
			dp[i] = 0
			return 0
		if dp[i] != -1:
			return dp[i]
		ans = 10 ** 8
		count = 0
		word = 0
		for j in range(i, n):
			count += nums[j]
			word += 1
			if word == 1:
				if count <= k:
					if j == n - 1:
						ans = 0
						break
					ans = min(ans, (k - count) ** 2 + self.solve(j + 1, n, nums, k, dp))
				else:
					break
			else:
				count += 1
				if count <= k:
					if j == n - 1:
						ans = 0
						break
					ans = min(ans, (k - count) ** 2 + self.solve(j + 1, n, nums, k, dp))
				else:
					break
			if j == n - 1:
				ans = 0
		dp[i] = ans
		return ans

	def solveWordWrap(self, nums, k):
		dp = [-1] * len(nums)
		return self.solve(0, len(nums), nums, k, dp)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [0] * n
		ans = [0] * n
		for i in range(n - 1, -1, -1):
			currlen = -1
			for j in range(i, n):
				currlen += nums[j] + 1
				if currlen > k:
					break
				if j == n - 1:
					cost = 0
				else:
					cost = (k - currlen) ** 2 + dp[j + 1]
				if dp[i] == 0 or cost < dp[i]:
					dp[i] = cost
					ans[i] = j
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):

		def solve(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			if nums[i] > rem:
				ans = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
			else:
				opt1 = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
				opt2 = solve(i + 1, rem - nums[i] - 1)
				ans = min(opt1, opt2)
			dp[i][rem] = ans
			return dp[i][rem]
		n = len(nums)
		dp = [[-1] * (k + 1) for i in range(n + 1)]
		return solve(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [float('INF')] * n
		dp[-1] = 0
		for i in range(n - 2, -1, -1):
			currlen = -1
			for j in range(i, n):
				currlen += nums[j] + 1
				if currlen > k:
					break
				if j == n - 1:
					dp[i] = 0
				else:
					dp[i] = min(dp[i], (k - currlen) ** 2 + dp[j + 1])
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		hmap = {}

		def solve(ind, curr, nums, k, n):
			if ind == n:
				return 0
			if (ind, curr) not in hmap:
				pick = 1000000000.0
				if nums[ind] <= curr:
					pick = solve(ind + 1, curr - nums[ind] - 1, nums, k, n)
				notpick = (curr + 1) ** 2 + solve(ind + 1, k - nums[ind] - 1, nums, k, n)
				hmap[ind, curr] = min(pick, notpick)
			return hmap[ind, curr]
		return solve(0, k, nums, k, n)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [[-1] * (k + 1) for i in range(n)]

		def findmincost(i, remk, k, n):
			if i == n - 1:
				if remk + 1 + nums[i] <= k:
					dp[i][remk] = 0
					return 0
				else:
					dp[i][remk] = (k - remk) * (k - remk)
					return (k - remk) * (k - remk)
			if dp[i][remk] != -1:
				return dp[i][remk]
			if remk == 0:
				dp[i][remk] = findmincost(i + 1, remk + nums[i], k, n)
				return dp[i][remk]
			else:
				if nums[i] + 1 + remk <= k:
					ans = findmincost(i + 1, remk + nums[i] + 1, k, n)
					ans = min(ans, (k - remk) * (k - remk) + findmincost(i + 1, nums[i], k, n))
				else:
					ans = (k - remk) * (k - remk) + findmincost(i + 1, nums[i], k, n)
				dp[i][remk] = ans
			return ans
		return findmincost(0, 0, k, n)


class Solution:

	def solveWordWrap(self, a, k):
		n = len(a)
		c = n * k ** 2
		dp = [0] * n
		end = [0] * n
		dp[n - 1] = 0
		end[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			dp[i] = c
			count = -1
			for j in range(i, n):
				count += 1 + a[j]
				if count > k:
					break
				if j == n - 1:
					dp[i] = 0
					end[i] = n - 1
					break
				else:
					cost = (k - count) ** 2 + dp[j + 1]
				if cost < dp[i]:
					dp[i] = cost
					end[i] = j
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [-1] * n

		def dfs(i):
			if dp[i] != -1:
				return dp[i]
			mn = float('inf')
			Sum = 0
			for idx in range(i, n):
				Sum += nums[idx]
				if Sum <= k and idx == n - 1:
					return 0
				elif Sum <= k:
					mn = min(mn, (k - Sum) * (k - Sum) + dfs(idx + 1))
				Sum += 1
			dp[i] = mn
			return dp[i]
		return dfs(0)


import sys

class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [0] * n
		ans = [0] * n
		dp[n - 1] = 0
		ans[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			currlen = -1
			dp[i] = sys.maxsize
			for j in range(i, n):
				currlen += nums[j] + 1
				if currlen > k:
					break
				if j == n - 1:
					cost = 0
				else:
					cost = (k - currlen) * (k - currlen) + dp[j + 1]
				if cost < dp[i]:
					dp[i] = cost
					ans[i] = j
		i = 0
		res = 0
		while i < n:
			pos = 0
			for j in range(i, ans[i] + 1):
				pos = pos + nums[j]
			x = ans[i] - i
			if ans[i] + 1 != n:
				res = res + (k - x - pos) ** 2
			i = ans[i] + 1
		return res


class Solution:

	def min_cost(self, nums, i, k, n, dp):
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		mn = float('inf')
		sum_ = 0
		for j in range(i, n):
			if sum_ + nums[j] + (j - i) > k:
				break
			if j == n - 1:
				mn = 0
			sum_ += nums[j]
			mn = min(mn, (k - sum_ - (j - i)) ** 2 + self.min_cost(nums, j + 1, k, n, dp))
		dp[i] = mn
		return dp[i]

	def solveWordWrap(self, nums, k):
		dp = [-1 for _ in range(n)]
		return self.min_cost(nums, 0, k, n, dp)


class Solution:

	def solveWordWrap(self, arr, k):
		n = len(arr)
		dp = [0] * n
		dp[n - 1] = 0
		for i in range(n - 2, -1, -1):
			cur = -1
			dp[i] = 10000000000.0
			for j in range(i, n):
				cur += arr[j] + 1
				if cur > k:
					break
				if j == n - 1:
					cost = 0
				else:
					cost = (k - cur) ** 2 + dp[j + 1]
				dp[i] = min(dp[i], cost)
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [[-1] * (k + 1) for q in range(n)]

		def recur(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			if nums[i] > rem:
				dp[i][rem] = (rem + 1) * (rem + 1) + recur(i + 1, k - nums[i] - 1)
				return dp[i][rem]
			else:
				choice1 = (rem + 1) * (rem + 1) + recur(i + 1, k - nums[i] - 1)
				choice2 = recur(i + 1, rem - nums[i] - 1)
				dp[i][rem] = min(choice1, choice2)
				return dp[i][rem]
		return recur(0, k)


def solver(arr, m, n, i, dct, k):
	if i == n:
		return 0
	if (i, k) in dct:
		return dct[i, k]
	cost = float('INF')
	if k < arr[i]:
		cost = k ** 2 + solver(arr, m, n, i + 1, dct, m - arr[i])
	elif k > arr[i]:
		if k < m:
			cost = k ** 2 + solver(arr, m, n, i + 1, dct, m - arr[i])
		if k == m:
			cost = min(cost, solver(arr, m, n, i + 1, dct, k - arr[i]))
		else:
			cost = min(cost, solver(arr, m, n, i + 1, dct, k - arr[i] - 1))
	elif arr[i] == m:
		cost = solver(arr, m, n, i + 1, dct, m - arr[i])
	else:
		cost = k ** 2 + solver(arr, m, n, i + 1, dct, m - arr[i])
	dct[i, k] = cost
	return cost

class Solution:

	def solveWordWrap(self, nums, k):
		dct = dict()
		return solver(nums, k, len(nums), 0, dct, k)


from math import inf

class Solution:

	def solveWordWrap(self, nums, k):
		dp = [inf for i in range(len(nums) + 1)]
		dp[-1] = 0
		for i in range(len(nums) - 1, -1, -1):
			(tot, spc_in_bet) = (0, -1)
			for j in range(i, len(nums)):
				tot += nums[j]
				spc_in_bet += 1
				if tot + spc_in_bet > k:
					break
				tmp = (k - (tot + spc_in_bet)) ** 2 if j + 1 != len(nums) else 0
				dp[i] = min(dp[i], tmp + dp[j + 1])
		return dp[0]


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def solveWordWrap(self, arr, k):

		def solve(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			ans = sys.maxsize
			if arr[i] > rem - 1:
				ans = rem * rem + solve(i + 1, k + 1 - arr[i] - 1)
			else:
				no = rem * rem + solve(i + 1, k + 1 - arr[i] - 1)
				yes = solve(i + 1, rem - arr[i] - 1)
				ans = min(yes, no)
			dp[i][rem] = ans
			return dp[i][rem]
		n = len(arr)
		dp = [[-1] * (k + 2) for i in range(0, n + 1)]
		return solve(0, k + 1)


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def solveWordWrap(self, arr, k):
		n = len(arr)

		def solve(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			if nums[i] > rem:
				ans = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
			else:
				opt1 = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
				opt2 = solve(i + 1, rem - nums[i] - 1)
				ans = min(opt1, opt2)
			dp[i][rem] = ans
			return dp[i][rem]
		n = len(nums)
		dp = [[-1] * (k + 1) for i in range(n + 1)]
		return solve(0, k)

		def solve(i, rem):
			if i == n or rem < -1:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			ans = sys.maxsize
			if arr[i] > rem:
				ans = (rem + 1) * (rem + 1) + solve(i + 1, k - arr[i] - 1)
			else:
				currline = solve(i + 1, rem - arr[i] - 1)
				notcurrline = (rem + 1) * (rem + 1) + solve(i + 1, k - arr[i] - 1)
				ans = min(currline, notcurrline)
			dp[i][rem] = ans
			return dp[i][rem]
		dp = [[-1 for j in range(0, k + 1)] for i in range(0, n + 1)]
		return solve(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [0] * n
		ans = [0] * n
		dp[n - 1] = 0
		ans[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			dp[i] = float('Inf')
			curLen = -1
			for j in range(i, n):
				curLen += nums[j] + 1
				if curLen > k:
					break
				if j == n - 1:
					cost = 0
				else:
					cost = (k - curLen) ** 2 + dp[j + 1]
				if dp[i] > cost:
					dp[i] = cost
					ans[i] = j
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		memo = {}

		def recursive(i, rem):
			key = (i, rem)
			if i == len(nums):
				memo[key] = 0
			if key in memo:
				return memo[key]
			if nums[i] > rem:
				memo[key] = (rem + 1) * (rem + 1) + recursive(i + 1, k - nums[i] - 1)
			else:
				ch1 = (rem + 1) * (rem + 1) + recursive(i + 1, k - nums[i] - 1)
				ch2 = recursive(i + 1, rem - nums[i] - 1)
				memo[key] = min(ch1, ch2)
			return memo[key]
		return recursive(0, k)


from functools import *

class Solution:

	def solveWordWrap(self, nums, k):
		dp = [[-1] * (k + 1) for i in range(len(nums))]

		def do(i, rl):
			if i == len(nums) - 1:
				ans = 0
				if nums[i] < rl:
					ans = 0
				else:
					ans = rl ** 2
				dp[i][rl] = ans
				return ans
			if dp[i][rl] != -1:
				return dp[i][rl]
			else:
				ans = 0
				if nums[i] < rl:
					ans = min(do(i + 1, rl - nums[i] if rl == k else rl - nums[i] - 1), rl ** 2 + do(i + 1, k - nums[i]))
				else:
					ans = rl ** 2 + do(i + 1, k - nums[i])
				dp[i][rl] = ans
				return ans
		return do(0, k)


import sys

class Solution:

	def solveWordWrap(self, arr, k):
		dp = [0] * n
		ans = [0] * n
		dp[n - 1] = 0
		ans[n - 1] = n - 1
		for i in range(n - 2, -1, -1):
			currlen = -1
			dp[i] = sys.maxsize
			for j in range(i, n):
				currlen += arr[j] + 1
				if currlen > k:
					break
				if j == n - 1:
					cost = 0
				else:
					cost = (k - currlen) * (k - currlen) + dp[j + 1]
				if cost < dp[i]:
					dp[i] = cost
					ans[i] = j
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		t = [[-1] * (k + 1) for i in range(n + 1)]

		def solve(i, rem):
			if i == len(nums):
				return 0
			if t[i][rem] != -1:
				return t[i][rem]
			ans = 0
			if nums[i] > rem:
				ans = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
			else:
				choice1 = (rem + 1) * (rem + 1) + solve(i + 1, k - nums[i] - 1)
				choice2 = solve(i + 1, rem - nums[i] - 1)
				ans = min(choice1, choice2)
			t[i][rem] = ans
			return t[i][rem]
		ans = solve(0, k)
		return ans


class Solution:

	def solveWordWrap(self, nums, k):
		dp = {}

		def dfs(i, limit):
			if i >= len(nums):
				return 0
			if (i, limit) in dp:
				return dp[i, limit]
			if nums[i] <= limit:
				take = dfs(i + 1, limit - nums[i] - 1)
				notTake = (limit + 1) ** 2 + dfs(i + 1, k - nums[i] - 1)
				dp[i, limit] = min(take, notTake)
			else:
				notTake = (limit + 1) ** 2 + dfs(i + 1, k - nums[i] - 1)
				dp[i, limit] = notTake
			return dp[i, limit]
		return dfs(0, k)


class Solution:

	def solveWordWrap(self, arr, k):
		n = len(nums)
		dp = [[-1] * (k + 1) for i in range(n + 1)]

		def fun2(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			ans = 0
			choice1 = 0
			choice2 = 0
			if nums[i] > rem:
				ans = (rem + 1) * (rem + 1) + fun2(i + 1, k - arr[i] - 1)
			else:
				choice1 = (rem + 1) * (rem + 1) + fun2(i + 1, k - arr[i] - 1)
				choice2 = fun2(i + 1, rem - arr[i] - 1)
				ans = min(choice1, choice2)
			dp[i][rem] = ans
			return dp[i][rem]
		res = fun2(0, k)
		return res


import functools

class Solution:

	def solveWordWrap(self, words, m):
		n = len(words)
		dp = {}

		def square(i):
			return i * i

		def fun(i, remL):
			if i == n - 1:
				return 0 if words[-1] < remL else square(remL)
			if dp.get((i, remL), -1) != -1:
				return dp[i, remL]
			opt1 = float('inf')
			if words[i] < remL:
				opt1 = fun(i + 1, remL - words[i] if remL == m else remL - words[i] - 1)
			opt2 = square(remL) + fun(i + 1, m - words[i])
			dp[i, remL] = min(opt1, opt2)
			return dp[i, remL]
		return fun(0, m)


class Solution:
	h = dict()

	def solve(self, csum, i, k):
		if i in self.h:
			return self.h[i]
		ans = float('inf')
		for j in range(i, n):
			a = csum[j] - (csum[i - 1] if i - 1 >= 0 else 0)
			l = j - i
			if a + l > k:
				break
			ans = min(ans, (k - a - l) ** 2 + self.solve(csum, j + 1, k) if j + 1 != len(csum) else 0)
		self.h[i] = ans
		return ans

	def solveWordWrap(self, nums, k):
		if len(nums) == 1:
			return 0
		n = len(nums)
		csum = [0] * n
		csum[0] = nums[0]
		for i in range(1, n):
			csum[i] = csum[i - 1] + nums[i]
		ans = self.solve(csum, 0, k)
		self.h.clear()
		return ans


import math

class Solution:

	def solveWordWrap(self, nums, k):
		dp = [math.inf for i in range(len(nums) + 1)]
		dp[0] = 0
		for i in range(1, len(nums) + 1):
			cost = 0
			for j in range(i, len(nums) + 1):
				cost += nums[j - 1]
				if cost > k:
					break
				if j < len(nums):
					total = k - cost
					total = total ** 2
					dp[j] = min(dp[j], dp[i - 1] + total)
				else:
					dp[j] = min(dp[j], dp[i - 1])
				cost += 1
		return dp[len(nums)]


class Solution:

	def solveWordWrap(self, arr, k):
		n = len(arr)

		def recursion(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			if arr[i] > rem:
				notPick = (rem + 1) * (rem + 1) + recursion(i + 1, k - arr[i] - 1)
				dp[i][rem] = notPick
			else:
				choice1 = recursion(i + 1, rem - arr[i] - 1)
				choice2 = (rem + 1) * (rem + 1) + recursion(i + 1, k - arr[i] - 1)
				dp[i][rem] = min(choice1, choice2)
			return dp[i][rem]
		dp = [[-1] * (k + 1) for i in range(n)]
		return recursion(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [0] * n
		sum = 0
		for ind in range(n - 1, -2, -1):
			if sum > 0:
				sum += 1
			if ind >= 0:
				sum += nums[ind]
				if sum > k:
					break
		for i in range(ind, -1, -1):
			sum = nums[i]
			dp[i] = pow(k - sum, 2) + dp[i + 1]
			for j in range(i + 1, n - 1):
				sum += nums[j] + 1
				if sum > k:
					break
				dp[i] = min(dp[i], pow(k - sum, 2) + dp[j + 1])
		return dp[0]


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [[-1] * (k + 1) for i in range(n)]

		def rec(i, rem):
			if i == n:
				return 0
			if dp[i][rem] != -1:
				return dp[i][rem]
			ans = 0
			if nums[i] > rem:
				ans = (rem + 1) ** 2 + rec(i + 1, k - nums[i] - 1)
			else:
				choice1 = (rem + 1) ** 2 + rec(i + 1, k - nums[i] - 1)
				choice2 = rec(i + 1, rem - nums[i] - 1)
				ans = min(choice1, choice2)
			dp[i][rem] = ans
			return dp[i][rem]
		return rec(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [[-1] * (k + 1) for _ in range(n + 1)]

		def recurse(index, cur_limit):
			if index == n:
				return 0
			if dp[index][cur_limit] != -1:
				return dp[index][cur_limit]
			if nums[index] <= cur_limit:
				take = recurse(index + 1, cur_limit - nums[index] - 1)
				not_take = (cur_limit + 1) * (cur_limit + 1) + recurse(index + 1, k - nums[index] - 1)
				dp[index][cur_limit] = min(take, not_take)
			else:
				not_take = (cur_limit + 1) * (cur_limit + 1) + recurse(index + 1, k - nums[index] - 1)
				dp[index][cur_limit] = not_take
			return dp[index][cur_limit]
		return recurse(0, k)


class Solution:

	def solveWordWrap(self, nums, k):
		dp = [-1 for i in range(len(nums) + 1)]

		def sol(arr, i, n, k):
			if i >= n - 1:
				return 0
			if dp[i] != -1:
				return dp[i]
			res = float('inf')
			s = 0
			for j in range(i, n):
				if j == i:
					s += arr[j]
				else:
					s += arr[j] + 1
				if s <= k:
					if j < n - 1:
						temp = (k - s) ** 2 + sol(arr, j + 1, n, k)
					else:
						temp = 0
					res = min(res, temp)
				else:
					break
			dp[i] = res
			return res
		res = sol(nums, 0, len(nums), k)
		return res


import sys
INT_MAX = sys.maxsize

class Solution:

	def solveWordWrap(self, nums, k):
		n = len(nums)
		dp = [-1] * n
		dp[n - 1] = 0
		for i in range(n - 2, -1, -1):
			dp[i] = INT_MAX
			curr_len = -1
			for j in range(i, n):
				curr_len += 1 + nums[j]
				if curr_len > k:
					break
				cost = 0
				if j == n - 1:
					cost = 0
				else:
					cost = (k - curr_len) * (k - curr_len) + dp[j + 1]
				if cost < dp[i]:
					dp[i] = cost
		return dp[0]


class Solution:

	def solveWordWrap(self, words, k):
		dp = {}

		def rec(i, remLength):
			if i >= len(words):
				dp[i, remLength] = 0
				return 0
			if (i, remLength) in dp:
				return dp[i, remLength]
			if remLength == k:
				dp[i, remLength] = rec(i + 1, k - words[i] - 1)
			elif i == len(words) - 1:
				if words[i] <= remLength:
					dp[i, remLength] = 0
				else:
					dp[i, remLength] = (remLength + 1) ** 2
			elif words[i] <= remLength:
				dp[i, remLength] = min((remLength + 1) ** 2 + rec(i + 1, k - words[i] - 1), rec(i + 1, remLength - words[i] - 1))
			else:
				dp[i, remLength] = (remLength + 1) ** 2 + rec(i + 1, k - words[i] - 1)
			return dp[i, remLength]
		rec(0, k)
		return dp[0, k]