ஒவ்வொரு உறுப்பு முந்தையதை விட இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ கொடுக்கப்பட்ட நீளத்தின் வரிசைகள்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் அமேசான் கோட்நேஷன் பேஸ்புக் கூகிள் பேபால் குவால்காம்
பிரித்து வெல்லுங்கள் டைனமிக் புரோகிராமிங்

“ஒவ்வொரு தனிமமும் முந்தையதை விட இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ இருக்கும் கொடுக்கப்பட்ட நீளத்தின் வரிசைமுறைகள்” என்ற சிக்கல் எங்களுக்கு m மற்றும் n ஆகிய இரண்டு முழு எண்களை வழங்குகிறது. இங்கே m என்பது வரிசையில் இருக்கக்கூடிய மிகப்பெரிய எண் மற்றும் தேவையான வரிசையில் இருக்க வேண்டிய உறுப்புகளின் எண்ணிக்கை. வரிசையில் மேலும் ஒரு நிபந்தனை விதிக்கப்பட்டுள்ளது, அதாவது ஒவ்வொரு உறுப்பு முந்தைய உறுப்புக்கு இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ இருக்க வேண்டும். அனைத்து நிபந்தனைகளும் பூர்த்தி செய்யப்படும் மொத்த வரிசைகளின் எண்ணிக்கையைக் கண்டறியவும்.

உதாரணமாக  

n = 3, m = 6
4

விளக்கம்

கொடுக்கப்பட்ட நிபந்தனைகளின் கீழ் 4 தொடர்கள் செய்யப்படலாம்: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

அணுகுமுறை  

ஒவ்வொரு உறுப்பு முந்தையதை விட இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ கொடுக்கப்பட்ட நீளத்தின் மொத்த வரிசைகளின் எண்ணிக்கையைக் கண்டுபிடிக்க சிக்கல் கேட்கிறது. அதிக நேர சிக்கலான ஒரு அப்பாவியாக தீர்வு என்பது நீளத்தின் அனைத்து வரிசைகளையும் உருவாக்குவதாகும் n. கூறுகள் ஏறுவரிசையை பின்பற்ற வேண்டும் மற்றும் அதிகபட்ச எண்ணிக்கை தாண்டக்கூடாது m. ஆனால் ஒவ்வொரு உறுப்புக்கும் முந்தையதை விட இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ இருக்க வேண்டும் என்ற உண்மையை நாம் இணைத்திருந்தால் இன்னும் திறமையான தீர்வு இருந்திருக்கலாம். இவ்வாறு நாம் ஒரு சுழல்நிலை சூத்திரத்தை எழுதலாம். நாங்கள் எடுத்தால் நாம் நீளத்துடன் வரிசையைக் கண்டுபிடிக்க வேண்டும் அன்-1 மற்றும் அதிகபட்ச உறுப்பு m / 2. இல்லையெனில் நாம் வரிசையுடன் நீளத்தைக் கண்டுபிடிக்க வேண்டும் மற்றும் அதிகபட்ச உறுப்பு மீ-1. இந்த அணுகுமுறை முன்னர் விவாதிக்கப்பட்டதை விட சற்று திறமையானதாக இருந்தாலும். இதுவும் நேரத்தை எடுத்துக்கொள்ளும்.

மேலும் காண்க
ஒரு சப்ரே ஒரு மலை வடிவத்தில் இருக்கிறதா இல்லையா என்பதைக் கண்டறியவும்

ஒவ்வொரு உறுப்பு முந்தையதை விட இரண்டு மடங்கு அதிகமாகவோ அல்லது சமமாகவோ கொடுக்கப்பட்ட நீளத்தின் வரிசைகள்முள்

நமக்கு ஒரு சுழல்நிலை சூத்திரம் உள்ள சந்தர்ப்பங்களில், நாங்கள் பயன்படுத்துகிறோம் டைனமிக் நிரலாக்க. மேற்கண்டவற்றை வெறுமனே நினைவில் கொள்வோம் சூத்திர நாங்கள் விவாதித்த தீர்வு. இந்த வழக்கில், எங்களுக்கு 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

ஒவ்வொரு உறுப்பு முந்தையதை விட இரண்டு அல்லது அதற்கு சமமாக இருக்கும் கொடுக்கப்பட்ட நீளத்தின் வரிசைகளைக் கண்டறிய ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது

ஓ (என் * எம்), ஏனெனில் சிக்கலுக்கான மாநிலங்கள் வரிசையின் நீளம் மற்றும் கருதக்கூடிய அதிகபட்ச எண்ணிக்கை. இதனால் நேர சிக்கலானது பல்லுறுப்புக்கோவை.

விண்வெளி சிக்கலானது

ஓ (என் * எம்), ஏனெனில் இடைநிலை முடிவுகளை சேமிக்க 2 டி டிபி அட்டவணையை உருவாக்கியுள்ளோம். விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.