N ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರಗಳ ಕನಿಷ್ಠ ಮೊತ್ತ  


ತೊಂದರೆ ಮಟ್ಟ ಹಾರ್ಡ್
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಕಪ್ಪು ಕಲ್ಲು ಜಿಇ ಹೆಲ್ತ್ಕೇರ್ JP ಮೋರ್ಗಾನ್ ಪೇಪಾಲ್
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್

“N ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರಗಳ ಕನಿಷ್ಠ ಮೊತ್ತ” ಸಮಸ್ಯೆ ನಿಮಗೆ n ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ಣಾಂಕಗಳು ಮತ್ತು ಒಂದು ಸಮಯದಲ್ಲಿ ಪಕ್ಕದಲ್ಲಿರುವ ಎರಡು ಅಂಶಗಳನ್ನು ತೆಗೆದುಕೊಂಡು ಒಂದೇ ಸಂಖ್ಯೆಯನ್ನು ಉಳಿಸುವವರೆಗೆ ಅವುಗಳ ಮೊತ್ತ ಮಾಡ್ 100 ಅನ್ನು ಹಿಂದಕ್ಕೆ ಇರಿಸುವ ಮೂಲಕ ನೀವು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರದ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡಬೇಕಾಗುತ್ತದೆ.

ಉದಾಹರಣೆ  

N ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರಗಳ ಕನಿಷ್ಠ ಮೊತ್ತಪಿನ್

10 20 30
1100

ವಿವರಣೆ

ಮೊದಲಿಗೆ, 10 ಅನ್ನು ಪಡೆಯಲು ನಾವು 20 ಮತ್ತು 200 ಅನ್ನು ಗುಣಿಸಿದಾಗ ನಂತರ ಹಿಂದಕ್ಕೆ ಇರಿಸಿ (10 + 20)% 100 = 30. ಈಗ ನಾವು [30, 30] ಹೊಂದಿದ್ದೇವೆ. ನಂತರ 30 * 30 = 900 ಅನ್ನು ಗುಣಿಸಿ. ಹೀಗೆ ಉತ್ತರ 900 + 200 = 1100.

ನಾವು ಮೊದಲು 20 ಮತ್ತು 30 ಅನ್ನು ಗುಣಿಸಿದ್ದರೆ ನಾವು (20 * 30) + (10 * 50) = 1100 ಗಳಿಸಿದ್ದೇವೆ. ಹೀಗೆ ಎರಡೂ ವಿಧಾನಗಳಲ್ಲಿ ನಾವು ಒಂದೇ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯುತ್ತಿದ್ದೆವು.

ಅಪ್ರೋಚ್  

ನೀವು ಕಂಡುಕೊಳ್ಳಬಹುದಾದ ಕನಿಷ್ಟ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ನಮ್ಮನ್ನು ಕೇಳುತ್ತದೆ, ಅಂದರೆ ನೀವು ಸಂಖ್ಯೆಗಳನ್ನು ಜೋಡಿಯಾಗಿ ಗುಣಿಸಿ ಮತ್ತು ನಂತರ ಅವುಗಳ ಸೇರ್ಪಡೆ ಮಾಡುತ್ತೀರಿ. ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಒಂದು ನಿಷ್ಕಪಟ ವಿಧಾನವನ್ನು ಬಳಸಲಾಗುತ್ತಿದೆ ಪುನರಾವರ್ತನೆ. ಎಲ್ಲಾ ಕ್ರಮಪಲ್ಲಟನೆಗಳನ್ನು ರಚಿಸಿ ಮತ್ತು ನಂತರ ಈ ಕ್ರಮಪಲ್ಲಟನೆಗಳು ಜೋಡಿಯಾಗಿ ಗುಣಿಸಬೇಕಾದ ಸೂಚ್ಯಂಕಗಳನ್ನು ಸೂಚಿಸುತ್ತವೆ ಎಂದು ಪರಿಗಣಿಸಿ. ಆದರೆ ಈ ವಿಧಾನವು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಏಕೆಂದರೆ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಪೀಳಿಗೆಯು ಅಪವರ್ತನೀಯ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ.

ಈ ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುವ ವಿಧಾನದ ಬದಲು, ಸಮಯದ ಮಿತಿಯಲ್ಲಿ ಫಲಿತಾಂಶವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಸಮರ್ಥವಾಗಿರುವ ಬೇರೆ ಯಾವುದೇ ಪರಿಹಾರದ ಬಗ್ಗೆ ನಾವು ಯೋಚಿಸಬೇಕು. ಈಗ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ನಮ್ಮ ಸಹಾಯಕ್ಕೆ ಬರುತ್ತದೆ. ಸ್ಟ್ಯಾಂಡರ್ಡ್ ಮೆಟ್ರಿಕ್ ಚೈನ್ ಗುಣಾಕಾರ ಸಮಸ್ಯೆಯ ಮೇಲೆ ಸಮಸ್ಯೆ ಸ್ವಲ್ಪ ವ್ಯತ್ಯಾಸವಾಗಿದೆ. ಇಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ ನಾವು ಮೊದಲು 2 ಅಂಶಗಳಿಗೆ, ನಂತರ 3 ಅಂಶಗಳಿಗೆ ಉತ್ತರವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತೇವೆ. ಆದ್ದರಿಂದ ನಾವು ಸೂಚ್ಯಂಕಗಳನ್ನು ಪುನರಾವರ್ತಿತ ಕಾರ್ಯದಲ್ಲಿ ಸಂಗ್ರಹಿಸಲು ಎರಡು ಅಸ್ಥಿರಗಳನ್ನು ಇಡುತ್ತೇವೆ ಅದು ಅನುಕ್ರಮದ ಗಡಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ನಂತರ ನಾವು ಅನುಕ್ರಮವನ್ನು 2 ಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಿದ್ದೇವೆ. ತದನಂತರ ಈ ಎರಡು ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಿ. ನಾವು ಬೇಸ್ ಕೇಸ್ ಅನ್ನು ಹೊಡೆಯುವವರೆಗೆ ಈ ಪ್ರಕ್ರಿಯೆಯು ಮುಂದುವರಿಯುತ್ತದೆ. ಎರಡೂ ಸೂಚ್ಯಂಕಗಳು ಒಂದೇ ಆಗಿರುವಾಗ ಇಲ್ಲಿ ಮೂಲ ಪ್ರಕರಣ. ಈ ಉಪಪ್ರೊಬ್ಲೆಮ್‌ಗಳಿಗೆ ಉತ್ತರವನ್ನು ನಾವು ಲೆಕ್ಕ ಹಾಕಿದಂತೆ ನಾವು ಆರಂಭಿಕ ಸಮಸ್ಯೆಯ ಫಲಿತಾಂಶವನ್ನು ಪಡೆಯಲು ಉತ್ತರಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತೇವೆ.

ಸಹ ನೋಡಿ
ಸೇತುವೆ ಮತ್ತು ಟಾರ್ಚ್ ಸಮಸ್ಯೆಯ ಕಾರ್ಯಕ್ರಮ

ಕೋಡ್  

N ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರಗಳ ಕನಿಷ್ಠ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include <bits/stdc++.h>
using namespace std;
int dp[5][5];
int sum(int i, int j, int a[]){
  int ans = 0;
  for (int k=i;k<=j;k++)
    ans=(ans+a[k])%100;
  return ans;
}

int minimumSum(int i, int j, int a[]){
    if(i==j)return 0;
  if (dp[i][j] != INT_MAX)
    return dp[i][j];
    // divide the problem into subproblems
  for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
  return dp[i][j];
}

int main() {
  int a[] = {10, 20, 30};
  int n = sizeof(a) / sizeof(a[0]);
  for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            dp[i][j] = INT_MAX;
  }
  cout<<minimumSum(0,n-1,a);
}
1100

N ಸಂಖ್ಯೆಗಳ ಗುಣಾಕಾರಗಳ ಕನಿಷ್ಠ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.*;
class Main{
  static int dp[][] = new int[5][5];
  static int sum(int i, int j, int a[]){
    int ans = 0;
    for (int k=i;k<=j;k++)
      ans=(ans+a[k])%100;
    return ans;
  }

  static int minimumSum(int i, int j, int a[]){
      if(i==j)return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];
      // divide the problem into subproblems
    for(int k=i;k<j;k++)
          dp[i][j] = Math.min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
    return dp[i][j];
  }

  public static void main(String[] args)
  {
    int a[] = {10, 20, 30};
    int n = a.length;
    for(int i=0;i<5;i++){
          for(int j=0;j<5;j++)
              dp[i][j] = Integer.MAX_VALUE;
    }
    int ans = minimumSum(0,n-1,a);
    	System.out.print(ans);
  	}
}
1100

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ  

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ 3), ಏಕೆಂದರೆ N ^ 2 ರಾಜ್ಯಗಳಿವೆ ಮತ್ತು ಪ್ರತಿಯೊಂದಕ್ಕೂ ಫಲಿತಾಂಶವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ನಾವು ಅಂದಾಜು N ಸಂಖ್ಯೆಯ ರಾಜ್ಯಗಳ ಮೇಲೆ ಅವಲಂಬಿತರಾಗಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ 2), ಏಕೆಂದರೆ ನಾವು 2 ಡಿ ಡಿಪಿ ಟೇಬಲ್ ಅನ್ನು ರಚಿಸಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.