Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lernen 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

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 3. Kapitel 1
single

single

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Suggested prompts:

Zusammenfassen Sie dieses Kapitel

Code in file erklären

Erklären, warum file die Aufgabe nicht löst

close

Awesome!

Completion rate improved to 8.33

bookProblem A. Binomial Coefficient

Swipe um das Menü anzuzeigen

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 desktopWechseln Sie zum Desktop, um in der realen Welt zu übenFahren Sie dort fort, wo Sie sind, indem Sie eine der folgenden Optionen verwenden
War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

close

Awesome!

Completion rate improved to 8.33
Abschnitt 3. Kapitel 1
single

single

some-alt