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

bookProblem 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

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 1
single

single

Spør AI

expand

Spør AI

ChatGPT

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

close

Awesome!

Completion rate improved to 8.33

bookProblem A. Binomial Coefficient

Sveip for å vise menyen

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 desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 3. Kapittel 1
single

single

some-alt