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

Stryg for at vise menuen

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 desktopSkift til skrivebord for at øve i den virkelige verdenFortsæt der, hvor du er, med en af nedenstående muligheder
Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 1
Vi beklager, at noget gik galt. Hvad skete der?

Spørg AI

expand
ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

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 desktopSkift til skrivebord for at øve i den virkelige verdenFortsæt der, hvor du er, med en af nedenstående muligheder
Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 3. Kapitel 1
Switch to desktopSkift til skrivebord for at øve i den virkelige verdenFortsæt der, hvor du er, med en af nedenstående muligheder
Vi beklager, at noget gik galt. Hvad skete der?
some-alt