ผลรวมขั้นต่ำของการคูณของจำนวน n


ระดับความยาก ยาก
ถามบ่อยใน แอคเซนเจอร์ แบล็ค GE Healthcare มอร์แกน JP บัตรเครดิต/เดบิต หรือ PayPal
แถว การเขียนโปรแกรมแบบไดนามิก

ปัญหา“ ผลรวมขั้นต่ำของการคูณของจำนวน n” ระบุว่าคุณได้รับ n จำนวนเต็ม และคุณต้องลดผลรวมของการคูณของตัวเลขทั้งหมดให้เหลือน้อยที่สุดโดยการเอาสององค์ประกอบที่อยู่ติดกันและใส่กลับ mod 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 ดังนั้นทั้งสองวิธีเราจะได้ผลลัพธ์เหมือนกัน

เข้าใกล้

ปัญหาขอให้เราหาผลรวมขั้นต่ำที่สามารถพบได้เพื่อให้คุณคูณตัวเลขเป็นคู่ ๆ ไปเรื่อย ๆ แล้วทำการบวก วิธีที่ไร้เดียงสาในการแก้ปัญหาคือการใช้ การเรียกซ้ำ. สร้างการเรียงสับเปลี่ยนทั้งหมดแล้วพิจารณาว่าการเรียงสับเปลี่ยนเหล่านี้แสดงถึงดัชนีที่ควรคูณเป็นคู่ แต่วิธีนี้ใช้เวลานานเนื่องจากการสร้างการเรียงสับเปลี่ยนมีความซับซ้อนของเวลาแฟกทอเรียล

แทนที่จะใช้วิธีการที่ใช้เวลานานนี้เราควรคิดถึงวิธีแก้ปัญหาอื่น ๆ ที่สามารถคำนวณผลลัพธ์ภายใต้เวลาที่กำหนดได้ ตอนนี้ การเขียนโปรแกรมแบบไดนามิก มาช่วยเรา ปัญหาคือการเปลี่ยนแปลงเล็กน้อยจากปัญหาการคูณ Matric Chain มาตรฐาน ในปัญหานี้ก่อนอื่นเราจะคำนวณคำตอบสำหรับ 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

รหัส Java เพื่อค้นหาผลรวมขั้นต่ำของการคูณของ 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 ดังนั้นความซับซ้อนของปริภูมิจึงเป็นพหุนามด้วย