DP hard
First two problems are from Leetcode Weekly Contest 95.
879. Profitable Schemes
“Well, it is a Knapsack problem and my first intuition is dp.
dp[i][j] means the count of schemes with i profit and j members.
The dp equation is simple here:
dp[i + p][j + g] += dp[i][j]) if i + p < P
dp[P][j + g] += dp[i][j]) if i + p >= P
Don’t forget to take care of overflow.
For each pair (p, g) of (profit, group), I update the count in dp.
Time Complexity:
O(NPG)
”
class Solution:
def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
# dp[g][p]
dp = [[0]*(G+1) for i in range(P+1)]
dp[0][0] = 1
for g, p in zip(group, profit):
for i in range(P, -1, -1):
for j in range(G-g, -1, -1):
dp[min(P, i+p)][j+g] += dp[i][j]
return sum(dp[P])%(10**9+7)877. Stone Game
C++ code from cui aoxiang
const int N = 500 + 10;
int dp[N][N][2];
class Solution {
public:
bool stoneGame(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n; ++i) {
dp[i][i][0] = a[i];
dp[i][i][1] = -a[i];
}
for (int k = 1; k < n; ++k) {
for (int i = 0; i + k < n; ++i) {
int j = i + k;
dp[i][j][0] = max(a[i] + dp[i + 1][j][1], a[j] + dp[i][j - 1][1]);
dp[i][j][1] = min(-a[i] + dp[i + 1][j][0], -a[j] + dp[i][j - 1][0]);
}
}
return dp[0][n - 1][0] > 0;
}
};873. Length of Longest Fibonacci Subsequence
https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
Complexity is around O(K*n²) where K is average number of valid fibonacci sequences ends at index i.
The idea is kind of brute force. Put all valid sequences into an open_list. For each item, following info will be recorded:
a, b, ending_idx, sequence_length.
a, b are the last two items of the sequence.
Then using DFS to find all valid sequences to solve the problem.
One trick to use is puting unique values of A[j:] to a dictionary to speed up the code. Specificly, we only add a new node to the open_list, if a+b can be found in the A[j+1:] where j is the index of b.
DFS(1192ms)
class Solution:
def lenLongestFibSubseq(self, A: List[int]) -> int:
vals_from_idx_i = collections.defaultdict(set)
vals_from_idx_i[len(A)-1] = {A[-1]}
for i in range(len(A)-1, -1, -1):
vals_from_idx_i[i] = vals_from_idx_i[i+1] | {A[i]}
def dfs():
fin_res = 2
open_list = []
for i in range(len(A)-2):
for j in range(i+1, len(A)-1):
new_a = A[i]+A[j]
if new_a in vals_from_idx_i[j+1]:
fin_res = 3
idx = A[j+1:].index(new_a)
open_list.append((A[j],new_a, j+idx+1, 3 ))
while open_list:
a,b, j, d = open_list.pop()
new_a = a+b
if new_a in vals_from_idx_i[j+1]:
if d+1>fin_res:
fin_res = d+1
idx = A[j+1:].index(new_a)
new_idx = j+idx+1
# early pruning
if d+1+(len(A)-1-new_idx)>fin_res:
open_list.append((b, new_a, new_idx, d+1))
return fin_res
fin_res = dfs()
return fin_res if fin_res>2 else 0DP(692ms)
class Solution:
def lenLongestFibSubseq(self, A: List[int]) -> int:
dp = collections.defaultdict(lambda : 2)
s = set(A)
for j in range(len(A)):
for i in range(j):
if A[j] - A[i] < A[i] and A[j] - A[i] in s:
dp[A[i], A[j]] = dp[(A[j] - A[i], A[i])] + 1
return max(dp.values() or [0])5304. XOR Queries of a Subarray
0 xor with 0 is still 0
even number of 1 XOR will be 0
odd number of 1 XOR will be 1
based on this, we can accumulate the number of “1” for each bit.
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
# the maximum number 10^9 has 30 bits
dp = [[0]*30 for _ in range(len(arr)+1)]
for i,a in enumerate(arr):
this_a = bin(a)[2:]
dp[i+1] = dp[i][:]
for j, c in enumerate(this_a[::-1]):
if c=='1':dp[i+1][-j-1] = dp[i][-j-1] + 1
res = []
for a,b in queries:
if a==b:
res.append(arr[a])
else:
xor_res = ['1' if (dp[b+1][k]-dp[a][k])&1 else '0' for k in range(30)]
this_res = int(''.join(xor_res), 2)
res.append(this_res)
return res5306. Minimum Insertion Steps to Make a String Palindrome
res of “abcda” = res of “bcd”
res of “bcd” = min (1+ res of “bc” , 1+res of “cd”)
class Solution:
def minInsertions(self, s: str) -> int:
from functools import lru_cache
@lru_cache(None)
def dp(l,r):
if l>=r:return 0
if s[l]==s[r]:return dp(l+1, r-1)
return min(dp(l, r-1), dp(l+1, r))+1
return dp(0, len(s)-1)hackerrank Coin change
Top down with comments
def getWays(n, c):
from functools import lru_cache
#top down
@lru_cache(None)
def dp(n, m):
if n < 0:return 0
if n == 0:return 1
if m < 0:return 0
# take this coin and not take this coin
# dp table
#n=4
#conins = [1 2 3]
# m=1 m=2 m=3
# n=4 dp(1,2)+dp(4,1)
# n=3
# n=2
# n=1 dp(0,0)+dp(1,-1) dp(-1,1)+dp(1,0) dp(-2, 2)+dp(1,1)
# dp(1,2) = dp(-2, 2)+dp(1,1) = dp(-2, 2)+dp(-1,1)+"dp(0,0)"+dp(1,-1) =0+0+1+0
# it means 1 + 3 which is 4
# dp(4,1) = dp(2,1) +dp(4,0) = dp(0,1)+dp(2,0)+dp(4,0) = dp(0,1)+dp(2,0)+dp(4,0)=1+1+1=3
# 2+2
# 2+1+1
# 1+1+1+1
return dp(n-c[m], m) + dp(n,m-1)
#for n in range(1,n+1):
# for m in range(len(c)):
# print(n,m, dp(n,m))
return dp(n, len(c)-1)Top down withou comments
def getWays(n, c):
from functools import lru_cache
@lru_cache(None)
def count_make_change(n, m):
if n < 0:return 0
if n == 0:return 1
if m <= 0:return 0
return count_make_change(n-c[m-1], m) + count_make_change(n,m-1)
return count_make_change(n, len(c))bottom up 2D array
counts = [[0]*m for _ in range(n+1)]
counts[0] = [1]*m
def dp_bottom_up(n,m):
for j in range(m):
for i in range(1,n+1):
# take it
if i-c[j]>=0:
counts[i][j] += counts[i-c[j]][j]
# do not take it
if j-1>=0:
counts[i][j] += counts[i][j-1]
return counts[n][m-1]
return dp_bottom_up(n,len(c))bottom up 1D array
def dp_bottom_up(n, m):
counts = [0] * (n+1)
counts[0] = 1
for i in range(m):
for j in range(c[i],n+1):
counts[j] += counts[j-c[i]]
return counts[n]
return dp_bottom_up(n, len(c))823. Binary Trees With Factors
Sort the list A at first. Scan A from small element to bigger.
DP equation:
dp[i] = sum(dp[j] * dp[i / j])
res = sum(dp[i])
with i, j, i / j in the list L
class Solution:
def numFactoredBinaryTrees(self, A: List[int]) -> int:
dp = {}
for a in sorted(A):
dp[a] = sum(dp[b] * dp.get(a // b, 0) for b in dp if a % b == 0) + 1
return sum(dp.values()) % (10**9 + 7)818. Race Car
https://leetcode.com/problems/race-car/
A nice summary can be found here
BFS
Runtime: 3020 ms, faster than 23.89% of Python3 online submissions for Race Car.
Memory Usage: 326 MB, less than 100.00% of Python3 online submissions for Race Car.
class Solution:
def racecar(self, target: int) -> int:
def bfs():
from collections import deque
Q = deque([(0,1,0)])
seen = {(0,1)}
if target==0:return 0
while True:
p, s, d = Q.popleft()
if p==target:return d
for action in [True, False]:
if action:
this_p = p+s
s*=2
if this_p==target:return d+1
if (this_p, s) not in seen:
seen.add((this_p, s))
Q.append((this_p, s,d+1))
else:
if s>0:s=-1
else:s=1
if (p,s) not in seen:
seen.add((p, s))
Q.append((p, s,d+1))
return bfs()If we change it to DP as shown here:
We get a much faster speed:
Runtime: 52 ms, faster than 93.36% of Python3 online submissions for Race Car.
Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Race Car.
class Solution:
def __init__(self):
self.dp = {0: 0}
def racecar(self, t: int) -> int:
if t in self.dp: return self.dp[t]
n = t.bit_length()
if 2**n - 1 == t: self.dp[t] = n
else:
self.dp[t] = self.racecar(2**n - 1 - t) + n + 1
for m in range(n - 1):
self.dp[t] = min(self.dp[t], self.racecar(t - 2**(n - 1) + 2**m) + n + m + 1)
return self.dp[t]We can use this code to print out the path to reach the target
class Solution:
def racecar(self, target: int) -> int:
def bfs():
from collections import deque
Q = deque([(0,1,0)])
print(0,1,0)
seen = {(0,1)}
if target==0:return 0
while True:
p, s, d = Q.popleft()
#print(p,s,d)
# True means A, False means R
for action in [True, False]:
if action:
print('A')
this_p = p + s
s <<= 1
if this_p==target:
print(this_p,s,d+1)
return d+1
if (this_p, s) not in seen:
print(this_p,s,d+1)
seen.add((this_p, s))
Q.append((this_p, s,d+1))
else:
print('R')
if s>0:s=-1
else:s=1
if (p,s) not in seen:
print(p,s,d+1)
seen.add((p, s))
Q.append((p, s,d+1))
return bfs()If target is -2, we will have output like this
0 1 0
A
1 2 1
R
0 -1 1
A
3 4 2
R
1 -1 2
A
-1 -2 2
R
A
7 8 3
R
3 -1 3
A
0 -2 3
R
1 1 3
A
-3 -4 3
R
-1 1 3
A
15 16 4
R
7 -1 4
A
2 -2 4
R
3 1 4
A
-2 -4 4When target is -5
0 1 0
1 2 1
0 -1 1
3 4 2
1 -1 2
-1 -2 2
7 8 3
3 -1 3
0 -2 3
1 1 3
-3 -4 3
-1 1 3
15 16 4
7 -1 4
2 -2 4
3 1 4
-2 -4 4
2 2 4
-7 -8 4
-3 1 4
0 2 4
-1 -1 4
31 32 5
15 -1 5
6 -2 5
7 1 5
0 -4 5
2 1 5
4 2 5
-6 -8 5
-2 1 5
4 4 5
2 -1 5
-15 -16 5
-7 1 5
-2 2 5
-3 -1 5
2 4 5
-2 -2 5
63 64 6
31 -1 6
14 -2 6
15 1 6
4 -4 6
6 1 6
8 2 6
-4 -8 6
3 2 6
6 4 6
4 -1 6
-14 -16 6
-6 1 6
-1 2 6
-2 -1 6
8 8 6
1 -2 6
-31 -32 6
-15 1 6
-6 2 6
-7 -1 6
0 4 6
-4 -2 6
6 8 6
-4 -4 6
127 128 7
63 -1 7
30 -2 7
31 1 7
12 -4 7
14 1 7
16 2 7
0 -8 7
4 1 7
7 2 7
6 -1 7
10 4 7
8 -1 7
-12 -16 7
-4 1 7
5 4 7
10 8 7
3 -2 7
-30 -32 7
-14 1 7
-5 2 7Then we can get some outputs shown below: each pair means
position, minimum step
-10 8
-9 9
-8 7
-7 4
-6 5
-5 7
-4 6
-3 3
-2 4
-1 2
0 0
1 1
2 4
3 2
4 5
5 7
6 5
7 3
8 6
9 8
10 7813. Largest Sum of Averages
Top down from
Runtime: 128 ms, faster than 94.43% of Python3 online submissions for Largest Sum of Averages.
Memory Usage: 13.6 MB, less than 66.67% of Python3 online submissions for Largest Sum of Averages.
from functools import lru_cache
class Solution:
def largestSumOfAverages(self, a: List[int], k: int) -> float:
@lru_cache(None)
def dp(st, k):
if k == 1:return sum(a[st:])/(len(a)-st)
total, res = 0, -float('inf')
for i in range(st, len(a)-k+1):
total += a[i]
res = max(res, (total/(i-st+1)) + dp(i+1, k-1))
return res
return dp(0, k)We can rewrite above code to
from functools import lru_cache
class Solution:
def largestSumOfAverages(self, a: List[int], k: int) -> float:
cusum = list(itertools.accumulate([0]+a))
@lru_cache(None)
def dp(i, k):
if k == 1:return (cusum[-1]-cusum[i])/(len(a)-i)
return max((cusum[j+1]-cusum[i])/(j-i+1) + dp(j+1, k-1) for j in range(i, len(a)-k+1))
return dp(0, k)Or
from functools import lru_cache
class Solution:
def largestSumOfAverages(self, a: List[int], k: int) -> float:
cusum = list(itertools.accumulate([0]+a))
@lru_cache(None)
def dp(i, k):
if i>=len(a):return 0
if k == 1:return (cusum[-1]-cusum[i])/(len(a)-i)
return max((cusum[j+1]-cusum[i])/(j-i+1) + dp(j+1, k-1) for j in range(i, len(a)))
return dp(0, k)bottom up from
https://leetcode.com/problems/largest-sum-of-averages/discuss/125872/Python-DP-solution
Runtime: 1260 ms, faster than 5.28% of Python3 online submissions for Largest Sum of Averages.Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Largest Sum of Averages.
solution
class Solution:
def largestSumOfAverages(self, A: List[int], K: int) -> float:
dp=[[0 for j in range(K)] for i in range(len(A))]
for j in range(len(A)):
for i in range(K):
if i==0:dp[j][i]=sum(A[:j+1])/len(A[:j+1])
else:
if len(A[:j+1])<i+1:break
for k in range(j):
dp[j][i]=max(dp[k][i-1]+sum(A[k+1:j+1])/len(A[k+1:j+1]),dp[j][i])
return dp[-1][-1]My own version bottom up solution
Runtime: 340 ms, faster than 43.48% of Python3 online submissions for Largest Sum of Averages.
Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for Largest Sum of Averages.
class Solution:
def largestSumOfAverages(self, a: List[int], k: int) -> float:
cusum = list(itertools.accumulate([0]+a))
N=len(a)
#dp[0][k] means from 0 to N-1 inclusively we have at most k groups
# dp[0][k] = maximum of below cases
#average(a[:1])+dp[1][k-1] from 1 to N-1 inclusively we have at most k-1 groups
#average(a[:2])+dp[2][k-1] from 2 to N-1 inclusively we have at most k-1 groups
#...
#average(a[:N-1])+dp[N-1][k-1] from N-1 to N-1 inclusively we have at most k-1 groups
# dp[1][k-1] from 1 to N-1 inclusively we have at most k-1 groups
# average(a[1:2])+dp[2][k-2]
# average(a[1:3])+dp[3][k-2]
# ...
# average(a[1:N-1])+dp[N-1][k-2]
# until now, the solution can be clear. We should maintain a 2D dp table
# dp[i][k] it means maximum average sum
# from index i to N-1 inclusively, we have at most k groups
# we can do it bottom up or top down
# we can use cusum to speed up the average operation.
dp = [[0]*(k+1) for i in range(len(a))]
# the very bottom case will be k is 1, it means we only have one group from i to N-1 inclusively
for at_most_group in range(1, k+1):
for begin_i in range(N):
if at_most_group == 1:
dp[begin_i][at_most_group] = (cusum[-1]-cusum[begin_i])/(N-begin_i)
else:
this_res = []
for j in range(begin_i, N):
# we divide at_most_group to 1+(at_most_group-1)
# (at_most_group-1) is already caculated.
# for eaxmple, dp[3][2] means
# we are dividing list a from index 3 to N-1 into at most 2 groups
# if we pick up index 3 to 4 as first group, then we still need dp[5][1]
# dp[5][1] means we begin from index 5, we need at most 1 group.
# dp[5][1] is already caculated as k is from smaller to larger.
first_group_ave = (cusum[j+1]-cusum[begin_i])/(j-begin_i+1)
if j+1<N:
this_res.append(first_group_ave+dp[j+1][at_most_group-1])
else:
this_res.append(first_group_ave)
dp[begin_i][at_most_group] = max(this_res)
# final result will be begin at 0 and at most it has k groups.
return dp[0][k]
