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))
Var allt tydligt?
Tack för dina kommentarer!
Avsnitt 3. Kapitel 1
single
Fråga AI
Fråga AI
Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal
Suggested prompts:
Sammanfatta detta kapitel
Explain code
Explain why doesn't solve task
Awesome!
Completion rate improved to 8.33Problem A. Binomial Coefficient
Svep för att visa menyn
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))
Byt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedanVar allt tydligt?
Tack för dina kommentarer!
Awesome!
Completion rate improved to 8.33Avsnitt 3. Kapitel 1
single
