box-lin / algorithm Goto Github PK
View Code? Open in Web Editor NEWmy notebook
License: MIT License
my notebook
License: MIT License
1. Meaning of dp[i][j]
2. Reoccurrence Formula
3. Dependencies Analysis
dp[i-1][j-1] | dp[i-1][j] |
---|---|
dp[i][j-1] | dp[i][j] |
Traversal should be left to right and top to down, so to compute the subproblem first.
4. Base Cases
The first row and the first column should be pre-computed.
Recursive
Time: NM + TM
class Solution:
def numWays(self, words: List[str], target: str) -> int:
mod = 10**9 + 7
m = len(words[0])
cnt = [[0]*26 for _ in range(m)]
for word in words:
for i, c in enumerate(word):
cnt[i][ord(c) - ord('a')] += 1
# di for char index of a word
# j for target
@cache
def dfs(di, j):
if j == len(target):
return 1
if di == m:
return 0
res = dfs(di+1, j) # not pick current di
charidx = ord(target[j]) - ord('a')
res += cnt[di][charidx] * dfs(di+1, j+1) # pick the current di
return res % mod
return dfs(0,0)
DP
class Solution:
def numWays(self, words: List[str], target: str) -> int:
I = len(words[0])
J = len(target)
mod = 10**9 + 7
cnt = [[0]*26 for _ in range(I)]
for word in words:
for i, c in enumerate(word):
cnt[i][ord(c) - ord('a')] += 1
dp = [ [0]*J for _ in range(I) ]
# dp[i][j] indicates num way to form target[..j] using word item[..i]
# base case
dp[0][0] = cnt[0][ord(target[0]) - ord('a')]
for i in range(1, I):
dp[i][0] += dp[i-1][0] + cnt[i][ord(target[0]) - ord('a')]
for i in range(1, I):
for j in range(1, J):
cidx = ord(target[j]) - ord('a')
dp[i][j] = ((dp[i-1][j-1]*cnt[i][cidx])%mod + dp[i-1][j])%mod
return dp[-1][-1]
Recursive Solution
class Solution:
def maxValueOfCoins(self, A: List[List[int]], K: int) -> int:
@cache
def dp(i, k):
if k == 0 or i == len(A): return 0
res, cur = dp(i + 1, k), 0 # Not to pick coin at this pile
for j in range(min(len(A[i]), k)): # Pick coin at this pile
cur += A[i][j]
res = max(res, cur + dp(i+1, k-j-1))
return res
return dp(0, K)
DP
class Solution:
"""
dp[i][j]: max value we pick at first i piles and with j coins
suppose we pick x coins at i piles
then to calculate the max value
dp[i][j] = max{dp[i-1][j-x] + presum[i][x] for x = 0,1,2,3 ... maxpick}
"""
def maxValueOfCoins(self, A: List[List[int]], k: int) -> int:
n = len(A)
dp = [ [0]*(k+1) for _ in range(n) ]
presum = [0] * n
for i in range(n):
cursum = 0
presum[i] = [cursum]
for j in range(len(A[i])):
cursum += A[i][j]
presum[i].append(cursum)
for i in range(n):
for j in range(k+1):
# suppose at current pile we pick x coins
maxpick = min(j, len(A[i])) + 1
for x in range(maxpick):
if i == 0:
dp[i][j] = presum[i][x]
else:
dp[i][j] = max(dp[i][j], dp[i-1][j-x] + presum[i][x])
return dp[n-1][k]
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.