Course Content
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))
Switch to desktop for real-world practiceContinue from where you are using one of the options belowEverything was clear?
Thanks for your feedback!
SectionΒ 3. ChapterΒ 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))
Switch to desktop for real-world practiceContinue from where you are using one of the options belowEverything was clear?
Thanks for your feedback!
SectionΒ 3. ChapterΒ 1
Switch to desktop for real-world practiceContinue from where you are using one of the options below