N സംഖ്യകളുടെ ഗുണനങ്ങളുടെ ഏറ്റവും കുറഞ്ഞ തുക  


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ഓട്ടോമോട്ടീവ് കറുത്ത പാറ GE ഹെൽത്ത്കെയർ ജെപി മോർഗൻ പേപാൽ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

“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 അക്കങ്ങളുടെ ഗുണനങ്ങളുടെ ഏറ്റവും കുറഞ്ഞ തുക കണ്ടെത്തുന്നതിന് C ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (N ^ 3), കാരണം N ^ 2 സംസ്ഥാനങ്ങളുണ്ട്, ഓരോന്നിനും ഫലം കണക്കുകൂട്ടാൻ ഞങ്ങൾ ഏകദേശ N സംസ്ഥാനങ്ങളെ ആശ്രയിച്ചിരിക്കുന്നു. അങ്ങനെ സമയ സങ്കീർണ്ണത പോളിനോമിയലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N ^ 2), കാരണം ഞങ്ങൾ ഒരു 2 ഡി ഡിപി പട്ടിക സൃഷ്ടിച്ചു. അതിനാൽ ബഹിരാകാശ സങ്കീർണ്ണതയും പോളിനോമിയൽ ആണ്.