Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Leer Problem A. Binomial Coefficient | Solutions
Dynamic Programming

Veeg om het menu te tonen

book
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))
copy

Switch to desktopSchakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties
Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 1

Vraag AI

expand
ChatGPT

Vraag wat u wilt of probeer een van de voorgestelde vragen om onze chat te starten.

book
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))
copy

Switch to desktopSchakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties
Was alles duidelijk?

Hoe kunnen we het verbeteren?

Bedankt voor je feedback!

Sectie 3. Hoofdstuk 1
Switch to desktopSchakel over naar desktop voor praktijkervaringGa verder vanaf waar je bent met een van de onderstaande opties
Onze excuses dat er iets mis is gegaan. Wat is er gebeurd?
some-alt