لږترلږه د شمیرو ضربونو شمیر


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي Accenture تورکاک په روبل روغتيا JP Morgan وی.دا
پیشه متحرک برنامې

ستونزه "د n شمیرو ضرب کولو لږترلږه مجموعه" وايي چې تاسو ته n ورکړل شوي ضمیمه او تاسو اړتیا لرئ د دوه عناصرو په نیولو سره چې په یو وخت کې سره نږدې دي او د دوی شمیره موډ 100 بیرته وساتئ تر هغه چې یوه شمیره پاتې نه وي د ټولو شمېرو ضرب الاجل کم کړئ.

بېلګه

لږترلږه د شمیرو ضربونو شمیر

10 20 30
1100

تشریح

لومړی ، موږ د 10 او 20 ترلاسه کولو لپاره 200 او 10 ضرب کړئ بیا یې بیرته واچوئ (20 + 100)٪ 30 = 30. اوس موږ [30 ، 30] لرو. بیا 30 * 900 = 900 ضرب کړئ. پدې توګه ځواب 200 + 1100 = XNUMX دی.

که موږ لومړی 20 او 30 ضرب کړي وای. موږ به (20 * 30) + (10 * 50) = 1100 ترلاسه کړی وی. په دې توګه دواړه لارې به موږ ورته پایله ترلاسه کړې وی.

او کړنلاره

ستونزه موږ څخه غوښتنه کوي چې لږترلږه پیسې ومومئ چې وموندل شي داسې چې تاسو په جوړو کې شمیرې ضرب کولو ته دوام ورکړئ او بیا یې اضافه کول ترسره کړئ. د ستونزې حل کولو لپاره یوه ناڅرګنده چلند کارول دي تکرار. ټولې اجازې تولید او بیا یې په پام کې ونیسئ چې دا جوازونه هغه شاخصونه په ګوته کوي چې باید په جوړه کې ضرب شي. مګر دا چلن وخت ضایع کوي ځکه چې د جوازونو تولید د واقعیت وخت پیچلتیا لري.

د دې وخت مصرفونکي چلند پرځای ، موږ باید د کوم بل حل په اړه فکر وکړو چې د وخت محدودیت لاندې پایلې محاسبه کولو وړ وي. اوس متحرک برنامې زموږ مرستې ته راځي. ستونزه د معیاري میټریک چین ضرب ستونزې په پرتله یو څه توپیر دی. دلته پدې ستونزه کې موږ لومړی د 2 عناصرو لپاره ځواب حساب کوو ، بیا د 3 عناصرو ، او داسې نور. نو موږ د تکراري فنکشن کې د شاخصونو ذخیره کولو لپاره دوه تغیرات ساتو کوم چې د ترتیب حد په نښه کوي. بیا وروسته موږ ترتیب په 2 برخو ویشلو. او بیا دا دوه فرعي ستونزې حل کړئ. دا پروسې تر هغه وخته پورې دوام لري چې موږ د اډې قضیه ټکوو. دلته د اساس قضیه هغه وخت ده کله چې دواړه شاخصونه یو شان وي. بیا لکه څنګه چې موږ د دې فرعي ستونزو لپاره ځواب محاسبه کړی دی موږ ځوابونه یوځای کوو ترڅو د لومړنۍ ستونزې لپاره د پایلو ترلاسه کولو لپاره.

کوډ

C ++ کوډ د 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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N ^ 3) ، ځکه چې دلته د N ^ 2 ایالتونه شتون لري او د هرې لپاره د پایلو د محاسبې لپاره موږ نږدې N حالتونو پورې تړاو لرو. په دې توګه د وخت پیچلتیا ډیره ده.

د ځای پیچلتیا

O (N ^ 2) ، ځکه چې موږ د 2D DP جدول رامینځته کړی. پدې توګه د ځای پیچلتیا هم ډیری پولی ده.