Послідовності заданої довжини, де кожен елемент більше або дорівнює дворазовому попередньому  


Рівень складності Легко
Часто запитують у Accenture Амазонка CodeNation Facebook Google PayPal компанія Qualcomm
Розділяй і володарюй Динамічне програмування

Завдання "Послідовності заданої довжини, де кожен елемент більше або дорівнює дворазовому попередньому", дає нам два цілих числа m і n. Ось m - найбільше число, яке може існувати в послідовності і - кількість елементів, які повинні бути присутніми в необхідній послідовності. Існує ще одна умова, накладена на послідовність, тобто кожен елемент повинен бути більше або дорівнює в два рази попередньому елементу. З’ясуйте загальну кількість послідовностей, щоб усі умови були дотримані.

Приклад  

n = 3, m = 6
4

Пояснення

Є 4 послідовності, які можна зробити за певних умов: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

Підхід  

Завдання просить нас знайти загальну кількість послідовностей заданої довжини, де кожен елемент більше або дорівнює вдвічі більше попереднього. Наївним рішенням, яке має складність у часі, може бути генерування всіх послідовностей довжини n. Елементи повинні слідувати за зростанням, і максимальна кількість не повинна перевищувати m. Але більш ефективним рішенням могло б бути, якби ми врахували той факт, що кожен елемент повинен бути більше або дорівнює подвійному попередньому. Таким чином, ми можемо написати рекурсивну формулу. Якщо ми виберемо тоді ми повинні знайти послідовність з довжиною н-1 і максимальний елемент м / 2. В іншому випадку нам потрібно знайти послідовність з довжиною і максимальний елемент м-1. Навіть незважаючи на те, що цей підхід є трохи ефективнішим, ніж раніше обговорюваний. Це теж трудомістко.

Дивись також
Знайдіть, чи є підмасив формою гори чи ні

Послідовності заданої довжини, де кожен елемент більше або дорівнює дворазовому попередньомуPin

У тих випадках, коли у нас є рекурсивна формула, ми використовуємо динамічне програмування. Ми просто запам’ятаємо вищезазначене рекурсивний рішення, яке ми обговорювали. У цьому випадку ми маємо 2 держави. Перше - це максимальне число, а друге - довжина послідовності.

код  

Код С ++ для пошуку послідовностей заданої довжини, де кожен елемент більше або дорівнює подвійному попередньому

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

Код Java для пошуку послідовностей заданої довжини, де кожен елемент більше або дорівнює подвійному попередньому

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

Аналіз складності  

Складність часу

O (N * M), оскільки стани задачі - це довжина послідовності та максимальна кількість, яку можна розглянути. Таким чином, часова складність поліноміальна.

Складність простору

O (N * M), оскільки ми створили 2D-таблицю DP для зберігання проміжних результатів. Складність простору також поліноміальна.