Contenido del Curso
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))
¡Gracias por tus comentarios!
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))
¡Gracias por tus comentarios!
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))
¡Gracias por tus comentarios!
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))