Problem A. Binomial Coefficient
Let's use the Memoization principle here. Let dp[i][j]
be a Binomial Coefficient C(i,j). First, dp
initialized with None
.
Given dp[n][k]
:
- if it is None, calculate it as
c(n-1, k-1) + c(n-1, k)
- if it is a base case:
k==0 or k==n
, thendp[n][k] = 1
- else return
dp[n][k]
Note that structure dp
depends on n
, and you must use it for defined n
.
123456789101112131415n = 200 dp = [[None for _ in range(n+1)] for _ in range(n+1)] def c(n, k): if k==0 or k==n: dp[n][k] = 1 if dp[n][k] == None: dp[n][k] = c(n-1, k)+c(n-1, k-1) return dp[n][k] print(c(3, 2)) print(c(10, 4)) print(c(11, 5)) print(c(144, 7))
Everything was clear?
Thanks for your feedback!
SectionΒ 3. ChapterΒ 1
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Awesome!
Completion rate improved to 8.33
Problem A. Binomial Coefficient
Swipe to show menu
Let's use the Memoization principle here. Let dp[i][j]
be a Binomial Coefficient C(i,j). First, dp
initialized with None
.
Given dp[n][k]
:
- if it is None, calculate it as
c(n-1, k-1) + c(n-1, k)
- if it is a base case:
k==0 or k==n
, thendp[n][k] = 1
- else return
dp[n][k]
Note that structure dp
depends on n
, and you must use it for defined n
.
123456789101112131415n = 200 dp = [[None for _ in range(n+1)] for _ in range(n+1)] def c(n, k): if k==0 or k==n: dp[n][k] = 1 if dp[n][k] == None: dp[n][k] = c(n-1, k)+c(n-1, k-1) return dp[n][k] print(c(3, 2)) print(c(10, 4)) print(c(11, 5)) print(c(144, 7))
Everything was clear?
Thanks for your feedback!
Awesome!
Completion rate improved to 8.33SectionΒ 3. ChapterΒ 1
single