Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Problem A. Binomial Coefficient | Solutions
Dynamic Programming
course content

Зміст курсу

Dynamic Programming

Dynamic Programming

1. Intro to Dynamic Programming
2. Problems
3. Solutions

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 desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

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

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 desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 3. Розділ 1
Switch to desktopПерейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів
Ми дуже хвилюємося, що щось пішло не так. Що трапилося?
some-alt