You are viewing a single comment's thread. Return to all comments →
Python solution based on @shehanjayalath's logic
def twoSubsequences(x, r, s): m = len(x) MOD = (10 ** 9) + 7 h, l = (r + s) // 2, (r - s) // 2 result = 0 dp = [[0 for i in range(m + 1)] for j in range(h + 1)] dp[0][0] = 1; if x[0] <= h: dp[x[0]][1] = 1 for i in range(1, m): for k in range(1, m + 1): dp[0][k] = 0 for j in range(h, 0, -1): dp[j][0] = 0 for k in range(1, m + 1): if j < x[i]: dp[j][k] = dp[j][k] else: dp[j][k] = (dp[j - x[i]][k - 1] + dp[j][k]) % MOD if l >= 0 and (r + s) % 2 != 1 and (r - s) % 2 != 1 and r != 0: for i in range(m): result = (result + (dp[h][i] * dp[l][i])) % MOD return result
Seems like cookies are disabled on this browser, please enable them to open this website
Wet Shark and Two Subsequences
You are viewing a single comment's thread. Return to all comments →
Python solution based on @shehanjayalath's logic