Помогите решить задачу на питоне

Question

Помогите решить задачу на питоне

あなたの自我を放っておいてください Ученик (51), на голосовании 7 месяцев назад

Перед вами в ряд лежит
n
шаров. У вас есть краски
k
разных цветов. Вы можете покрасить любой шар в любой цвет, красок каждого цвета бесконечно. Сколько существует способов раскрасить шары так, чтобы никакие два соседних шара не были покрашены в одинаковый цвет? Каждый шар должен быть покрашен в один из
k
цветов.

Формат входных данных
Даны два целых числа
n
и
k
, по одному на строке (
1
≤
n
≤
1000
,
2
≤
k
≤
1000
).

Формат результата
Выведите одно число — ответ на задачу.

Примеры
Входные данные
2
2
Результат работы
2

Answer 1

 
# Считываем входные данные 
n = int(input()) 
k = int(input()) 
# Инициализируем список для хранения количества способов раскрасить шары 
dp = [0] * (n + 1) 
# Базовый случай: 1 способ раскрасить 1 шар в k цветов 
dp[1] = k 
# Заполняем список dp с использованием динамического программирования 
list(map(lambda i: dp.__setitem__(i, (k - 1) * (dp[i - 1] + dp[i - 2])), range(2, n + 1))) 
 
# Выводим результат 
print(dp[n])

и упрощенном коде

 n = int(input()) 
k = int(input()) 
dp = [0] * (n + 1) 
dp[1] = k 
list(map(lambda i: dp.__setitem__(i, (k - 1) * (dp[i - 1] + dp[i - 2])), range(2, n + 1))) 
print(((k - 1) * (dp[n - 1] + dp[n - 2])) if n > 1 else k)

Результат

Answer 2

Светлана Мещенко Ученик (158) 7 месяцев назад

воспользуйся формулой
k * (k-1)**(n-1)

Дмитрий МельниковЗнаток (315) 6 месяцев назад

Все верно! Но почему???