Data-structures 05

1

dp[i][j] = dp[i-1][j] or (j >= A[i-1] and dp[i-1][j - A[i-1]])

---

2

dp[i] = min(dp[i], dp[i - v[j]] + 1) if dp[i] is not None else dp[i - v[j]] + 1

---

3

for j in range(max(0, i - L), i):
	dp[i] = dp[j] and T(S, j, i - 1)
	# or
	if dp[j] and T(S, j, i - 1):
		dp[i] = True
		break # continue to next i

---

4

for i in range(0, n):
	# expression of length one is just the value itself 
	dpmax[i][i] = num[i]
	dpmin[i][i] = num[i]
# for each possible length of the sub-expression
for len in range(2, n + 1):
	# for each possible starting index i
	for i in range(0, n - len):
		# endind index j is calculated based on start and length
		j = i + len - 1
		# some initial value of "unknown", can be inf and -inf
		dpmax[i][j] = None
		dpmin[i][j] = None
		# for each k, split sub-expression into two parts up to k and after k
		# this imitates the placement of parenthesis around left and right parts
		for k in range(i, j):
			leftmax = dpmax[i][k]
			leftmin = dpmin[i][k]
			rightmax = dpmax[k + 1][j]
			rightmin = dpmin[k + 1][j]
 
			# operator(operation) between left and right 
			operator = op[k]
			curmax = 0
			curmin = 0
			if operator == "+":
				# maximize and minimize sum
				curmax = leftmax + rightmax
				curmin = leftmin + rightmin
			else:
				# maximize and minimize difference
				curmax = leftmax - rightmin
				curmin = leftmin - rightmax
 
			dpmax[i][j] = max(dpmax[i][j], curmax) if dpmax[i][j] is not None else curmax
			dpmin[i][j] = max(dpmin[i][j], curmin) if dpmin[i][j] is not None else curmin