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, then dp[n][k] = 1
else return dp[n][k]

Note that structure dp depends on n, and you must use it for defined n.


              123456789101112131415
            
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))

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 3. Розділ 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, then dp[n][k] = 1
else return dp[n][k]

Note that structure dp depends on n, and you must use it for defined n.


              123456789101112131415
            
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))

Все було зрозуміло?

Секція 3. Розділ 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, then dp[n][k] = 1
else return dp[n][k]

Note that structure dp depends on n, and you must use it for defined n.


              123456789101112131415
            
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))

Все було зрозуміло?

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, then dp[n][k] = 1
else return dp[n][k]

Note that structure dp depends on n, and you must use it for defined n.


              123456789101112131415
            
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))

Секція 3. Розділ 1