จำนวนส่วนสูงสุดของความยาว a, b และ c


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน แบล็ค ByteDance ซิทริกซ์ Google Teradata Uber
การเขียนโปรแกรมแบบไดนามิก

ปัญหา“ จำนวนส่วนสูงสุดของความยาว a, b และ c” ระบุว่าคุณได้รับจำนวนเต็มบวก N และคุณต้องหาจำนวนส่วนสูงสุดของความยาว a, b และ c ที่สามารถสร้างได้โดยใช้ N

ตัวอย่าง

จำนวนส่วนสูงสุดของความยาว a, b และ c

N = 7
a = 5, b = 2, c = 3
3

คำอธิบาย

ที่นี่ถ้าเราใช้วิธีโลภพยายามตัดส่วนทั้งหมดด้วยส่วนที่เล็กที่สุด (= 2) เราจะไม่สามารถสร้างส่วนสุดท้ายของขนาด 1 ได้ดังนั้นเราจึงแบ่งความยาว 4 ด้วยสองส่วนความยาว 2 ส่วนและส่วนความยาว 4 ส่วนหนึ่งส่วน

เข้าใกล้

ปัญหาให้จำนวนเต็มบวก N และจำนวนเต็มอื่น ๆ a, b, c ในที่นี้เราต้องการหารจำนวนตามความยาวของ a, b และ c เราต้องหาร N เพื่อให้จำนวนเซ็กเมนต์สูงสุด ดังนั้นเพื่อแก้ปัญหาก่อนอื่นเรามาลองใช้วิธีโลภ วิธีแก้ปัญหาด้วยความโลภคือการเลือก a, b และ c ที่เล็กที่สุด ตอนนี้เราแบ่ง N ออกเป็นส่วนที่มีความยาวต่ำสุด แต่มีสิ่งที่จับได้ว่าถ้าส่วนที่เล็กที่สุดไม่หาร N? จากนั้นเราจะเหลือส่วนที่เหลือซึ่งไม่สามารถทำได้ ดังนั้นนี่เป็นการยืนยันว่าเราไม่สามารถหาคำตอบโดยใช้วิธีโลภได้ในบางกรณี

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

รหัส

รหัส C ++ เพื่อค้นหาจำนวนส่วนสูงสุดของความยาว a, b และ c

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

int main()
{
  int n = 7, a = 5, b = 2, c = 3;
  int dp[n + 1];
  memset(dp, -1, sizeof(dp));
  // base case
  dp[0] = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] != -1) {
            if(i + a <= n )dp[i + a] = max(dp[i] + 1, dp[i + a]);
            if(i + b <= n )dp[i + b] = max(dp[i] + 1, dp[i + b]);
            if(i + c <= n )dp[i + c] = max(dp[i] + 1, dp[i + c]);
    }
  }
    cout<<dp[n];
}
3

โค้ด Java เพื่อค้นหาจำนวนเซ็กเมนต์สูงสุดของความยาว a, b และ c

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    int n = 7, a = 5, b = 2, c = 3;
    int dp[] = new int[n+1];
    for(int i=0;i<=n;i++)dp[i] = -1;
    // base case
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
      if (dp[i] != -1) {
              if(i + a <= n )dp[i + a] = Math.max(dp[i] + 1, dp[i + a]);
              if(i + b <= n )dp[i + b] = Math.max(dp[i] + 1, dp[i + b]);
              if(i + c <= n )dp[i + c] = Math.max(dp[i] + 1, dp[i + c]);
      }
    }
    System.out.println(dp[n]);
  }
}
3

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

บน), เพราะเราวิ่งวนไปเรื่อย ๆ จนถึงจำนวนเต็มที่กำหนด ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

ความซับซ้อนของอวกาศ

บน), เนื่องจากเราต้องสร้างอาร์เรย์ 1D DP สำหรับจัดเก็บผลลัพธ์ระดับกลางเพื่อหลีกเลี่ยงการคำนวณซ้ำ ดังนั้นความซับซ้อนของพื้นที่จึงเป็นเส้นตรงด้วย