Contenu du cours
Dynamic Programming
Dynamic Programming
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.
n = 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))
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousTout était clair ?
Merci pour vos commentaires !
Section 3. Chapitre 1
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.
n = 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))
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousTout était clair ?
Merci pour vos commentaires !
Section 3. Chapitre 1
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous