ಪ್ರತಿ ಅಂಶವು ಹಿಂದಿನ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿರುವ ನಿರ್ದಿಷ್ಟ ಉದ್ದದ ಅನುಕ್ರಮಗಳು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಅಮೆಜಾನ್ ಕೋಡ್‌ನೇಷನ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಪೇಪಾಲ್ ಕ್ವಾಲ್ಕಾಮ್
ಭಾಗಿಸಿ ಜಯಿಸಿ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

"ಪ್ರತಿ ಅಂಶವು ಹಿಂದಿನ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿರುವ ನಿರ್ದಿಷ್ಟ ಉದ್ದದ ಅನುಕ್ರಮಗಳು" ಎಂಬ ಸಮಸ್ಯೆ ನಮಗೆ m ಮತ್ತು n ಎಂಬ ಎರಡು ಪೂರ್ಣಾಂಕಗಳನ್ನು ಒದಗಿಸುತ್ತದೆ. ಇಲ್ಲಿ m ಅನುಕ್ರಮದಲ್ಲಿ ಅಸ್ತಿತ್ವದಲ್ಲಿರಬಹುದಾದ ದೊಡ್ಡ ಸಂಖ್ಯೆ ಮತ್ತು ಅಗತ್ಯವಿರುವ ಅನುಕ್ರಮದಲ್ಲಿ ಇರಬೇಕಾದ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಅನುಕ್ರಮದ ಮೇಲೆ ಇನ್ನೂ ಒಂದು ಷರತ್ತು ವಿಧಿಸಲಾಗಿದೆ, ಅಂದರೆ ಪ್ರತಿಯೊಂದು ಅಂಶವು ಹಿಂದಿನ ಅಂಶಕ್ಕಿಂತ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿರಬೇಕು. ಎಲ್ಲಾ ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸುವ ಒಟ್ಟು ಅನುಕ್ರಮಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ.

ಉದಾಹರಣೆ

n = 3, m = 6
4

ವಿವರಣೆ

ನಿರ್ದಿಷ್ಟ ಪರಿಸ್ಥಿತಿಗಳಲ್ಲಿ 4 ಅನುಕ್ರಮಗಳನ್ನು ಮಾಡಬಹುದು: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

ಅಪ್ರೋಚ್

ಒಂದು ನಿರ್ದಿಷ್ಟ ಉದ್ದದ ಒಟ್ಟು ಅನುಕ್ರಮಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳುತ್ತದೆ, ಅಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಅಂಶವು ಹಿಂದಿನ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಅಥವಾ ಸಮವಾಗಿರುತ್ತದೆ. ಹೆಚ್ಚಿನ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುವ ನಿಷ್ಕಪಟ ಪರಿಹಾರವೆಂದರೆ ಉದ್ದದ ಎಲ್ಲಾ ಅನುಕ್ರಮಗಳನ್ನು ಉತ್ಪಾದಿಸುವುದು n. ಅಂಶಗಳು ಆರೋಹಣ ಕ್ರಮವನ್ನು ಅನುಸರಿಸಬೇಕು ಮತ್ತು ಗರಿಷ್ಠ ಸಂಖ್ಯೆ ಮೀರಬಾರದು m. ಆದರೆ ಪ್ರತಿಯೊಂದು ಅಂಶವು ಹಿಂದಿನ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚು ಅಥವಾ ಸಮನಾಗಿರಬೇಕು ಎಂಬ ಅಂಶವನ್ನು ನಾವು ಸೇರಿಸಿಕೊಂಡರೆ ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ಪರಿಹಾರವಾಗಬಹುದು. ಹೀಗೆ ನಾವು ಪುನರಾವರ್ತಿತ ಸೂತ್ರವನ್ನು ಬರೆಯಬಹುದು. ನಾವು ಆರಿಸಿದರೆ ನಂತರ ನಾವು ಉದ್ದವನ್ನು ಹೊಂದಿರುವ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು n-1 ಮತ್ತು ಗರಿಷ್ಠ ಅಂಶ m / 2. ಇಲ್ಲದಿದ್ದರೆ ನಾವು ಉದ್ದವನ್ನು ಹೊಂದಿರುವ ಅನುಕ್ರಮವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಮತ್ತು ಗರಿಷ್ಠ ಅಂಶ M-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 ಡಿ ಡಿಪಿ ಟೇಬಲ್ ಅನ್ನು ರಚಿಸಿದ್ದೇವೆ. ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.