Рубрики

Количество различных способов выразить N как сумму 1, 3 и 4

Учитывая N, посчитайте количество способов выразить N как сумму 1, 3 и 4.

Примеры:

Input :  N = 4
Output : 4 
Explanation: 1+1+1+1 
             1+3
             3+1 
             4 

Input : N = 5 
Output : 6
Explanation: 1 + 1 + 1 + 1 + 1
             1 + 4
             4 + 1
             1 + 1 + 3
             1 + 3 + 1
             3 + 1 + 1

Подход: разделите проблему на подзадачи для ее решения. Пусть DP [n] будет числом способов записать N как сумму 1, 3 и 4. Рассмотрим одно возможное решение с n = x1 + x2 + x3 +… xn. Если последнее число равно 1, то сумма оставшихся чисел равна n-1. Таким образом, число, которое заканчивается на 1, равно DP [n-1]. Принимая во внимание другие случаи, когда последнее число равно 3 и 4. Окончательное повторение будет:

DPn = DPn-1 + DPn-3 + DPn-4
Base case :
DP[0] = DP[1] = DP[2] = 1 and DP[3] = 2

C ++

// Программа CPP для иллюстрации количества
// способы представления N как суммы 1, 3 и 4.
#include <bits/stdc++.h>

using namespace std;

  
// функция для подсчета количества
// способы представить n как сумму 1, 3 и 4

int countWays(int n)

{

    int DP[n + 1];

  

    // базовые случаи

    DP[0] = DP[1] = DP[2] = 1;

    DP[3] = 2;

  

    // итерация для всех значений от 4 до n

    for (int i = 4; i <= n; i++) 

        DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4];

      

    return DP[n];

}

  
// код драйвера

int main()

{

    int n = 10;

    cout << countWays(n);

    return 0;

}

Джава

// Java-программа для иллюстрации
// количество способов представления
// N как сумма 1, 3 и 4.

  

class GFG {

  

    // Функция для подсчета

    // количество способов представления

    // n как сумма 1, 3 и 4

    static int countWays(int n)

    {

        int DP[] = new int[n + 1];

  

        // базовые случаи

        DP[0] = DP[1] = DP[2] = 1;

        DP[3] = 2;

  

        // итерация для всех значений от 4 до n

        for (int i = 4; i <= n; i++)

            DP[i] = DP[i - 1] + DP[i - 3

                    + DP[i - 4];

  

        return DP[n];

    }

  

    // код драйвера

    public static void main(String[] args)

    {

        int n = 10;

        System.out.println(countWays(n));

    }

}

  
// Этот код добавлен
// Прерной Сайни.

python3

# Программа Python для иллюстрации количества
# способы представления N как суммы 1, 3 и 4.

  
# Функция для подсчета количества
# способов представить n как сумму 1, 3 и 4

def countWays(n):

  

    DP = [0 for i in range(0, n + 1)]

      

    # базовые случаи

    DP[0] = DP[1] = DP[2] = 1

    DP[3] = 2

  

    # Итерация для всех значений от 4 до n

    for i in range(4, n + 1):

        DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]

      

    return DP[n]

  

      
# Код драйвера

n = 10

print (countWays(n))

  
# Этот код предоставлен Gitanjali.

C #

// C # программа для иллюстрации
// количество способов представления
// N как сумма 1, 3 и 4.

using System;

  

class GFG {

  

    // Функция для подсчета

    // количество способов представления

    // n как сумма 1, 3 и 4

    static int countWays(int n)

    {

        int []DP = new int[n + 1];

  

        // базовые случаи

        DP[0] = DP[1] = DP[2] = 1;

        DP[3] = 2;

  

        // итерация для всех значений от 4 до n

        for (int i = 4; i <= n; i++)

            DP[i] = DP[i - 1] + DP[i - 3] 

                    + DP[i - 4];

  

        return DP[n];

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 10;

        Console.WriteLine(countWays(n));

    }

}

  
// Этот код добавлен
// от vt_m.

PHP

<?php
// PHP программа для иллюстрации
// количество способов
// представим N как сумму
// 1, 3 и 4.

  
// функция для подсчета
// количество способов
// представим n как сумму
// 1, 3 и 4

function countWays($n)

{

    $DP = array();

  

    // базовые случаи

    $DP[0] = $DP[1] = $DP[2] = 1;

    $DP[3] = 2;

  

    // повторяем для всех

    // значения от 4 до n

    for ($i = 4; $i <= $n; $i++) 

        $DP[$i] = $DP[$i - 1] + 

                  $DP[$i - 3] + 

                  $DP[$i - 4];

      

    return $DP[$n];

}

  
// Код драйвера

$n = 10;

echo countWays($n);

  
// Этот код добавлен
// Sam007
?>


Выход:

64

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Рекомендуемые посты:

Количество различных способов выразить N как сумму 1, 3 и 4

0.00 (0%) 0 votes