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))
Tout était clair ?
Merci pour vos commentaires !
Section 3. Chapitre 1
single
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Suggested prompts:
Résumer ce chapitre
Expliquer le code dans file
Expliquer pourquoi file ne résout pas la tâche
Awesome!
Completion rate improved to 8.33
Problem A. Binomial Coefficient
Glissez pour afficher le 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))
Tout était clair ?
Merci pour vos commentaires !
Awesome!
Completion rate improved to 8.33Section 3. Chapitre 1
single