# A DP problem solved by using a Knapsack problem way

This is this week’s biweekly contest problem. The solution is pretty similar to the Knapsack problem.

# Explanation

`words = ["acca","bbbb","caca"], target = "aba"`

we firstly can get the following information

for the character ‘a’, for the location of different indexes, it has the following number of words:

for a:

index 0: [‘acca’]

index 1: [‘caca’]

index 2: []

index 3: [‘acca’, ‘caca’]

for b:

index 0: [‘bbbb’]

index 1: [‘bbbb’]

index 2: [‘bbbb’]

index 3: [‘bbbb’]

For the above example, we can have a DP table as below

0 1 2 3 a. 1 1 0 2

b. 0 1*1. 1*(1+1) 1*(1+1+0)

a 0 0. 0*(...) 2*(0+1+2)

We can use a natively 2D DP without optimization.

# A naively 2D DP without optimization

It has the time complexity of O(mn*m) as we don’t have the optimization.

It got TLE.

**85 / 89** test cases passed.

`# time complexity O(mnm), space O(mn)`

class Solution:

def numWays(self, words: List[str], target: str) -> int:

s = set(target)

d = collections.defaultdict(lambda : collections.defaultdict(int))

for word in words:

for i, char in enumerate(word):

if char in s:d[char][i] += 1

n = len(target)

m = len(words[0])

dp = [[0]*m for _ in range(n)]

dp[0] = [d[target[0]][j] for j in range(m)]

for i in range(1, n):

for j in range(i, m):

dp[i][j] = d[target[i]][j]*sum(dp[i-1][k] for k in range(j))

return sum(dp[-1])%(10**9 + 7)

# A naively 2D DP with time complexity optimization

We can use a prefix sum to optimize the time complexity as O(mn)

`# time complexity O(mn), space O(mn)`

class Solution:

def numWays(self, words: List[str], target: str) -> int:

s = set(target)

d = collections.defaultdict(lambda : collections.defaultdict(int))

for word in words:

for i, char in enumerate(word):

if char in s:d[char][i] += 1

n = len(target)

m = len(words[0])

dp = [[0]*m for _ in range(n)]

dp[0] = [d[target[0]][j] for j in range(m)]

for k in range(1, m):

dp[0][k] += dp[0][k-1]

for i in range(1, n):

for j in range(i, m):

dp[i][j] = d[target[i]][j]*dp[i-1][j-1]

for k in range(i + 1, m):

dp[i][k] += dp[i][k-1]

return dp[-1][-1]%(10**9 + 7)

# Bottom UP DP with time/space complexity optimization

`# time complexity O(mn), space O(m)`

class Solution:

def numWays(self, words: List[str], target: str) -> int:

s = set(target)

d = collections.defaultdict(lambda : collections.defaultdict(int))

for word in words:

for i, char in enumerate(word):

if char in s:d[char][i] += 1

n = len(target)

m = len(words[0])

dp = [1]*m

for i in range(n):

new_dp = [0]*m

for j in range(i, m):

new_dp[j] = dp[j-1]*d[target[i]][j]

for k in range(i, m):

if k > 0: new_dp[k] += new_dp[k-1]

dp = new_dp

return dp[-1]%(10**9 + 7)

Thanks for reading.