קאַטינג אַ רוט


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן דירעקטי פליפּקאַרט גוגל דזשפּ מאָרגאַן מייקראָסאָפֿט
דינאַמיש פּראָגראַממינג

פּראָבלעם סטאַטעמענט

די פּראָבלעם "קוטטינג אַ רוט" שטאַטן אַז איר באַקומען אַ רוט פון עטלעכע לענג און פּרייסיז פֿאַר אַלע סיזעס פון ראַדז וואָס זענען קלענערער ווי אָדער גלייַך צו די אַרייַנשרייַב לענג. מיר וויסן אַז די פּרייַז פֿאַר רוטז פון לענג פון 1 צו n, ווייַל די לענג פון די רוט איז געווען n. איין זאַך צו באַמערקן דאָ איז אַז די פּרייַז פֿאַר די רוט פון פאַרשידענע לענגקטס איז נישט גלייַך פונאנדערגעטיילט. עטלעכע ראַדז מיט אַ זיכער לענג האָבן העכער פּרייסיז ווי אנדערע. די ראַדז קען אָדער קען האָבן מער לענג קאַמפּערד מיט אנדערע ראַדז פון פאַרשידענע לענגקטס.

בייַשפּיל

length = 1 2 3 4 5 6 7
price = 4 5 6 7 7 1 1
28

 

קאַטינג אַ רוטדערקלערונג: דער בעסטער וואָס מיר קענען טאָן איז צו נעמען 7 רוטז לענג וואָס קענען געבן אונדז די בעסטער רעזולטאַט פון קאָסטן 28.

צוגאַנג

אַזוי צו לייזן דעם פּראָבלעם, איר קענען טראַכטן פון סאַלווינג דעם פּראָבלעם רעקורסיוועלי. און דער צוגאַנג איז פערלי ריכטיק. אַזוי לאָזן מיר דיסקוטירן ווי אַזוי מיר קענען סאָלווע די פּראָבלעם מיט רעקורסיאָן. מיר קענען פּרובירן צו שנייַדן די רוט אין סעגמאַנץ פון פאַרשידענע לענגקטס. דערנאָך מיר רעכענען די פּרייַז פֿאַר ראַדז וואָס זענען געשאפן נאָך קאַטינג אַלע ראַדז. אָבער ווען מיר זאָגן אַז מיר דאַרפֿן צו געפֿינען אַלע די וועגן פון קאַטינג די ראַדז. די אָפּעראַציע איז זייער טייַער און האט עקספּאָונענשאַל צייט קאַמפּלעקסיטי. אַזוי מיר דאַרפֿן צו עפעס רעדוצירן די קאַמפּיאַטיישאַנז. אַ אָפּטימיזאַטיאָן קען זיין אויב מיר לייגן די פּרייַז פון אַ אָפּשניט פון די רוט אין די צייט פון קאַטינג. דערנאך סאָלווע די פּראָבלעם ווידער מיט אַ קלענערער רוט. אָבער דאָס איז נישט גוט גענוג, דעם אַלגערידאַם נעמט נאָך עקספּאָונענשאַל צייט.

די רעקורסיווע פאָרמולע פֿאַר קאַטינג אַ רוט פּראָבלעם איז

cuttingRod(n) = max(cost[i] + cuttingRod(n-i-1)) where i is in range from 0 to n-1

אַזוי, אויב מיר נעמען אַ קורץ מאָמענט צו זען ווי די אַלגערידאַם אַרבעט. מיר קענען זען אַז מיר רופן קאַטינג ראָד (n-1), קאַטינג ראָד (n -2),…, קאַטינג ראָד (1) וואָס דאַן ווידער האלט אויף קאַטינג ראָד. זינט קאַטינגראָד (i) איז גערופֿן קייפל מאָל. עס איז בעסער אויב מיר סטאָרד די וואַלועס. אַזוי מיר וועלן נוצן דינאַמיש פּראָגראַממינג צו רעדוצירן די ומנייטיק קאַמפּיאַטיישאַנז.

קאָדעקס

C ++ קאָד פֿאַר קאַטינג רוט

#include<bits/stdc++.h>
using namespace std;

int cuttingRod(vector<int> &cost) 
{
  int n = cost.size();
  int dp[n+1]; dp[0] = 0;

  for(int i=1;i<=n;i++){
    dp[i] = INT_MIN;
    for(int j=0;j<i;j++)
      dp[i] = max(dp[i], cost[j]+dp[i-j-1]);
  }
  return dp[n];
} 

int main(){
  // length of input rod
  int n;cin>>n;
  // store prices for length 1 to n
  vector<int> cost(n);
  for(int i=0;i<n;i++)
    cin>>cost[i];
  int maxCost = cuttingRod(cost);
  cout<<maxCost;
}
7
4 5 6 7 7 1 1
28

Java קאָד פֿאַר קאַטינג רוט

import java.util.*;
class Main{
  
  static int cuttingRod(ArrayList<Integer> cost){
    int n = cost.size();
    int dp[] = new int[n+1];
    dp[0] = 0;

    for(int i=1;i<=n;i++){
      dp[i] = Integer.MIN_VALUE;
      for(int j=0;j<i;j++)
        dp[i] = Math.max(dp[i], cost.get(j)+dp[i-j-1]);
    }
    return dp[n];
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // length of input rod
    int n = sc.nextInt();
    // store prices for length 1 to n
    ArrayList<Integer> cost = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      cost.add(a);
    }
    int maxCost = cuttingRod(cost);
    System.out.println(maxCost);
  }
}
7
4 5 6 7 7 1 1
28

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N ^ 2)ווייַל מיר נוצן אַ דפּ צוגאַנג פון דנאָ-אַרויף און פאָרזעצן צו דערהייַנטיקן די קאָס פון ראַדז פון קלענערער לענג. דאָס אַלאַוז רידוסינג די פּראָבלעם וואָס איז סאַלווד אין עקספּאָונענשאַל צייט צו פּאַלינאָומיאַל צייט.

ספעיס קאַמפּלעקסיטי

אָ (N), ווייַל דער פּלאַץ איז געניצט פֿאַר סטאָרינג די וואַלועס אין דפּ טיש.