Tất cả thử thách
Khó 1 đã giải Tỷ lệ chấp nhận 100.0%

Matrix Chain Multiplication

Find the cheapest order to multiply a chain of matrices.

Bạn sẽ học được gì

  • Định nghĩa QHĐ trên các chuỗi con
  • Thử mọi điểm chia
  • Tối thiểu chi phí nhân

Đề bài

Matrix i has size dimensions[i] × dimensions[i+1]. Multiplying a p×q matrix by a q×r matrix costs p·q·r scalar multiplications. Choose where to put parentheses so multiplying the whole chain costs the least.

Implement min_multiplications(dimensions).

Input

dimensions: n + 1 sizes describing n matrices.

Output

Return the minimum total cost.

Ràng buộc

2 ≤ length of dimensions ≤ 200; 1 ≤ each size ≤ 500

Ví dụ

Ví dụ 1
Đầu vào:
dimensions = [10, 30, 5, 60]

Kết quả mong đợi:
expected = 4500
Đầu vào:
std::vector<long long> dimensions = {10, 30, 5, 60};

Kết quả mong đợi:
long long expected = 4500;
Đầu vào:
long[] dimensions = new long[] {10, 30, 5, 60};

Kết quả mong đợi:
long expected = 4500;

Giải thích

(A×B)×C costs 10·30·5 + 10·5·60 = 4500, cheaper than A×(B×C) = 27000.

Ví dụ 2
Đầu vào:
dimensions = [5, 10]

Kết quả mong đợi:
expected = 0
Đầu vào:
std::vector<long long> dimensions = {5, 10};

Kết quả mong đợi:
long long expected = 0;
Đầu vào:
long[] dimensions = new long[] {5, 10};

Kết quả mong đợi:
long expected = 0;

Giải thích

A single matrix needs no multiplication: 0.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Thứ tự nhân ma trận làm thay đổi tổng chi phí dù kích thước ma trận kết quả vẫn như nhau.

Gợi ý 2

Thử mọi điểm chia cho mỗi đoạn và tái sử dụng kết quả của các đoạn nhỏ hơn.

Gợi ý 3

Dùng mảng kích thước cẩn thận: mỗi bài toán con phụ thuộc vào các đầu mút quanh các ma trận, không chỉ riêng số lượng ma trận.

Độ phức tạp mong đợi

thời gian O(n^3), bộ nhớ phụ O(n^2)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 777 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.