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

Обычный код на Python для твоего задания :

 def count_subsets(n): 
    dp = [1] * (n + 1)  # Инициализация массива 
    for i in range(1, n + 1): 
        if i >= 2: 
            dp[i] += dp[i - 2]  # Добавляем подмножества, исключая элемент i-2 
        if i >= 3: 
            dp[i] += dp[i - 3]  # Добавляем подмножества, исключая элемент i-3 
    return sum(dp) 
 
n = int(input("Введите n: ")) 
print(count_subsets(n)) 

Улучшенный :

 def count_subsets(n): 
    if n < 0: 
        return 0  # Нет подмножеств для отрицательного n 
    if n == 0: 
        return 1  # Только пустое подмножество для n = 0 
 
    # Использование переменных для хранения количества вместо массива 
    count_0 = 1  # dp[0] 
    count_1 = 1  # dp[1] 
    count_2 = 2 if n >= 2 else count_1  # dp[2] 
     
    for i in range(3, n + 1): 
        current_count = count_0 + count_1 + count_2 
        count_0, count_1, count_2 = count_1, count_2, current_count 
 
    return count_2 
 
n = int(input("Enter n: ")) 
print(count_subsets(n)) 

Улучшения :

1. Оптимизация памяти

Вместо использования списка dp для хранения всех значений до n, мы отслеживаем только последние три подсчета (count_0, count_1 и count_2). Это снижает сложность памяти с O(n) до O(1).

1. Ясность и логика

Функция теперь явно обрабатывает случаи, когда n меньше или равен нулю. Она возвращает 0 для отрицательных значений и 1 для n = 0, что соответствует пустому подмножеству.
Цикл начинается с 3, так как мы уже обрабатываем случаи для n = 0, n = 1 и n = 2.

1. Производительность

Исключая ненужные проверки внутри цикла и непосредственно вычисляя текущий подсчет на основе предыдущих подсчетов, мы упрощаем процесс.