Blog

Quy hoạch động là gì, và nó được mô tả như thế nào?

Quy hoạch động (DP) là một kỹ thuật thuật toán thường dựa trên một công thức truy hồi và một (hoặc một vài) trạng thái khởi đầu. Một lời giải con của bài toán được xây dựng từ các lời giải trước đó. Các thuật toán DP có độ phức tạp đa thức, giúp đảm bảo thời gian chạy nhanh hơn nhiều so với các kỹ thuật khác như quay lui (backtracking) hay brute-force.

Bây giờ, hãy tìm hiểu cơ sở của quy hoạch động thông qua một ví dụ:

Cho một danh sách gồm \(N\) đồng xu với giá trị \(V_1, V_2, ..., V_N\) và một tổng số tiền cần đạt được là \(S\). Hãy tìm số lượng đồng xu ít nhất sao cho tổng của chúng bằng \(S\) (có thể sử dụng một đồng xu nhiều lần), hoặc kết luận rằng không thể chọn được tập hợp đồng xu thỏa mãn điều kiện.

Bây giờ, chúng ta sẽ bắt đầu xây dựng một lời giải DP:

Trước hết, chúng ta cần tìm một trạng thái mà tại đó ta có thể xác định được lời giải tối ưu và sử dụng nó để tìm lời giải tối ưu cho các trạng thái tiếp theo.

Trạng thái (“state”) có nghĩa là gì?

Trạng thái là một cách để mô tả một tình huống, một lời giải con của bài toán. Ví dụ, một trạng thái có thể là lời giải cho tổng \(i\), trong đó \(i \leq S\).

Một trạng thái nhỏ hơn trạng thái \(i\) sẽ là lời giải cho bất kỳ tổng nào \(j\), với \(j < i\).

Để tìm trạng thái \(i\), trước tiên ta cần tìm tất cả các trạng thái nhỏ hơn \(i\), tức là các trạng thái \(j\) với \(j < i\).

Khi đã tìm được số lượng đồng xu ít nhất để tạo ra tổng \(i\), ta có thể dễ dàng tìm được trạng thái tiếp theo – lời giải cho tổng \(i+1\).

Làm thế nào để tìm được trạng thái?

Cách tìm rất đơn giản:
- Với mỗi đồng xu \(j\) sao cho \(V_j \leq i\), ta xem số lượng đồng xu ít nhất đã tìm được cho tổng \(i - V_j\) (vì trước đó ta đã tính toán cho tổng này).
- Giả sử số đồng xu tối thiểu cần thiết để tạo tổng \(i - V_j\) là \(m\). Nếu \(m + 1\) nhỏ hơn số đồng xu tối thiểu hiện tại của tổng \(i\), ta cập nhật kết quả mới cho tổng \(i\).

Ví dụ minh họa

Cho các đồng xu có giá trị: \(1, 3, 5\).
Tổng cần đạt được: \(S = 11\).

1. Khởi tạo trạng thái ban đầu:

   • Với tổng 0, số đồng xu tối thiểu là 0.
   • Với các tổng khác, chưa có lời giải, nên gán giá trị ban đầu là \(\infty\).

2. Xét tổng \(S = 1\):

   • Chỉ có đồng xu 1 nhỏ hơn hoặc bằng 1.
   • Xét tổng 1 - 1 = 0, ta đã có lời giải cho tổng 0 là 0 đồng xu.
   • Khi thêm đồng xu 1, ta có tổng 1 với 1 đồng xu → Cập nhật Min[1] = 1.

3. Xét tổng \(S = 2\):

   • Chỉ có đồng xu 1 nhỏ hơn hoặc bằng 2.
   • Tổng 2 - 1 = 1 có lời giải là 1 đồng xu.
   • Thêm đồng xu 1, tổng 2 cần 2 đồng xu → Min[2] = 2.

4. Xét tổng \(S = 3\):

   • Có 2 đồng xu khả dụng: 1, 3.
   • Dùng đồng xu 1: tổng 3 - 1 = 2 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 3: tổng 3 - 3 = 0 có lời giải 0 đồng xu. Thêm 1 đồng xu → 1 đồng xu.
   • Chọn lời giải tối ưu → Min[3] = 1.

5. Xét tổng \(S = 4\):

   • Dùng đồng xu 1: tổng 4 - 1 = 3 có lời giải 1 đồng xu. Thêm 1 đồng xu → 2 đồng xu.
   • Dùng đồng xu 3: tổng 4 - 3 = 1 có lời giải 1 đồng xu. Thêm 1 đồng xu → 2 đồng xu.
   • Cả hai cách đều cho 2 đồng xu → Min[4] = 2.

6. Xét tổng \(S = 5\):

   • Dùng đồng xu 1: tổng 5 - 1 = 4 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 3: tổng 5 - 3 = 2 có lời giải 2 đồng xu. Thêm 1 đồng xu → 3 đồng xu.
   • Dùng đồng xu 5: tổng 5 - 5 = 0 có lời giải 0 đồng xu. Thêm 1 đồng xu → 1 đồng xu.
   • Chọn lời giải tối ưu → Min[5] = 1.

Tiếp tục với tổng 6, 7, …, 11 theo cách tương tự.

Kết quả cuối cùng

Sau khi tính toán, số đồng xu ít nhất để tạo tổng \(11\) là \(3\) đồng xu: \(5, 5, 1\).

Dãy con không giảm dài nhất

Đến thời điểm này, chúng ta đã thảo luận về những ví dụ rất đơn giản.

Bây giờ, hãy tìm cách chuyển từ trạng thái này sang trạng thái khác trong các bài toán khó hơn. Để làm điều đó, chúng ta sẽ giới thiệu một khái niệm mới gọi là công thức truy hồi (recurrent relation), giúp kết nối giữa một trạng thái nhỏ hơn và một trạng thái lớn hơn.

Cho một dãy gồm \(N\) số: \(A[1], A[2], ..., A[N]\). Hãy tìm độ dài lớn nhất của dãy con không giảm.

Bước 1: Xác định trạng thái

Như đã thảo luận trước đó, chúng ta cần xác định một trạng thái (“state”) thể hiện một bài toán con, và từ đó tìm ra lời giải cho nó.
Trong hầu hết các trường hợp, một trạng thái phụ thuộc vào các trạng thái trước đó (nhỏ hơn nó) và không bị ảnh hưởng bởi các trạng thái lớn hơn.

Chúng ta định nghĩa trạng thái \(S[i]\) là độ dài của dãy con không giảm dài nhất kết thúc tại phần tử \(A[i]\).

• Trạng thái \(S[i]\) chỉ chứa thông tin về độ dài dãy con, không quan tâm đến các số phía sau nó.
• Khi \(i < j\), trạng thái \(S[i]\) không bị thay đổi khi tính toán \(S[j]\).

Bước 2: Công thức truy hồi

• Khởi tạo: Ban đầu, mỗi phần tử đều có thể tạo thành một dãy con riêng lẻ, do đó: \(S[i] = 1, \quad \text{với mọi } i\)
• Chuyển trạng thái:
  Với mỗi \(j < i\), ta kiểm tra xem có thể mở rộng dãy con không giảm hay không:
  • Nếu \(A[j] \leq A[i]\) (tức là dãy con vẫn không giảm), ta có thể mở rộng \(S[j]\) bằng cách thêm \(A[i]\).
  • Nếu \(S[j] + 1 > S[i]\), ta cập nhật: \(S[i] = S[j] + 1\)

Như vậy, ta duyệt qua từng phần tử \(i\), tìm trạng thái tối ưu dựa trên các trạng thái trước đó.

Ví dụ minh họa

Xét dãy số:

Kết quả cuối cùng: Dãy con không giảm dài nhất có độ dài 4.

Một số bài tập vận dụng

1. Bài toán chiếc balo 5
2. Bài toán dãy con tăng dài nhất
3. Bài toán xâu con chung dài nhất

Nguồn: Dynamic Programming - From Novice to Advanced

Trong lập trình chuyên nghiệp, việc đặt tên cho biến, hàm, và lớp là rất quan trọng để đảm bảo mã nguồn dễ đọc, dễ hiểu và dễ bảo trì. Dưới đây là một số tiêu chuẩn chung cho việc đặt tên:

1. Biến (Variables)

• Camel Case: Sử dụng cho biến cục bộ hoặc biến trong phương thức. Từ đầu tiên viết thường, các từ tiếp theo viết hoa chữ cái đầu.

  • Ví dụ: studentName, totalAmount, isActive.

• Snake Case: Thường dùng cho các biến toàn cục hoặc biến hằng.

  • Ví dụ: MAX_HEIGHT, MIN_WIDTH, global_variable.

2. Hàm (Functions/Methods)

• Camel Case: Tương tự như biến, các hàm thường dùng Camel Case với chữ cái đầu của từ đầu tiên viết thường và các từ tiếp theo viết hoa chữ cái đầu.

  • Ví dụ: calculateTotal(), getUserInfo(), processData().

• Mô tả hành động: Tên hàm nên miêu tả hành động hoặc chức năng mà hàm thực hiện.

  • Ví dụ: sendEmail(), validateInput(), fetchData().

3. Lớp (Classes)

• Pascal Case: Viết hoa chữ cái đầu của tất cả các từ.

  • Ví dụ: Student, OrderManager, UserProfile.

• Danh từ: Tên lớp nên là một danh từ hoặc một cụm danh từ vì lớp thường đại diện cho một thực thể.

  • Ví dụ: Invoice, Car, DatabaseConnection.

4. Giao diện (Interfaces)

• Pascal Case: Tương tự như lớp, nhưng thường bắt đầu bằng chữ “I”.
  • Ví dụ: IUserService, IDatabaseConnection, IShape.

5. Module và File

• Snake Case hoặc Kebab Case: Thường dùng cho tên file và module.
  • Ví dụ: user_profile.py, order_manager.js, data-processing.go.

6. Quy tắc chung

• Ngắn gọn và mô tả: Tên nên ngắn gọn nhưng đủ mô tả để người đọc có thể hiểu được ý nghĩa mà không cần đọc chi tiết bên trong.
• Tránh viết tắt không cần thiết: Chỉ sử dụng viết tắt khi chúng thực sự phổ biến và dễ hiểu.
• Tuân thủ quy ước của ngôn ngữ: Mỗi ngôn ngữ lập trình có những quy ước riêng, vì vậy nên tuân thủ theo các quy ước đó.

Ví dụ tổng quát

# Python

class Student:
    def __init__(self, student_name, student_id):
        self.student_name = student_name
        self.student_id = student_id

    def get_full_name(self):
        return f"{self.student_name} (ID: {self.student_id})"

MAX_AGE = 100
min_height = 150

def calculate_average(grades):
    total = sum(grades)
    return total / len(grades)

// Java

public class Student {
    private String studentName;
    private int studentId;

    public Student(String studentName, int studentId) {
        this.studentName = studentName;
        this.studentId = studentId;
    }

    public String getFullName() {
        return studentName + " (ID: " + studentId + ")";
    }
}

public interface IUserService {
    void createUser(User user);
    User getUserById(int userId);
}

Những quy tắc này không phải là cố định và có thể thay đổi tùy theo ngôn ngữ và phong cách của dự án. Tuy nhiên, việc tuân thủ các tiêu chuẩn này giúp mã nguồn trở nên nhất quán và dễ quản lý hơn.

CÁC LỚP HỌC LẬP TRÌNH

Trung tâm TMath Edu liên tục tuyển sinh các lớp lập trình (Online và offline):

• Lập trình Scratch cơ bản, nâng cao, ôn thi tin học trẻ bảng A
• Lập trình C++ cơ bản, nâng cao, ôn thi học sinh giỏi, ôn thi chuyên tin
• Lập trình Python.

Thông tin liên hệ:

SĐT: 0947.771.736 - 0983.420.518 - 0973.044.327

Địa chỉ: Nhà 9, ngõ 6, đường Nguyễn Thị Minh Khai, TP Vinh, tỉnh Nghệ An

Bài số 1:

Học lập trình cho người mới bắt đầu

Bài số 2:

Học lập trình cần trang bị những gì

Bài số 3:

Lập trình C++

Nhằm tạo điều kiện cho học sinh tiểu học rèn luyện và giao lưu ngôn ngữ lập trình Scratch. Trung tâm Tmath Edu hỗ trợ câu lạc bộ Tre Vàng tổ chức giao lưu Tin học trẻ cho học sinh Tiểu học lần II năm 2022.

Thời gian: 9h – 11h sáng chủ nhật, ngày 18/12/2022.

Thi trực tuyến tại hệ thống của trung tâm: https://p.tmath.vn/ (tương tự hệ thống thi của BTC Tin học trẻ toàn quốc).

Kính mời quý thầy/cô, PHHS đăng kí cho các em HS tham gia giao lưu, trải nghiệm và chuẩn bị sẵn sàng cho cuộc thi Tin học trẻ các cấp sắp tới.

Link đăng ký: ĐĂNG KÝ TẠI ĐÂY

Lưu ý: Tất cả đều miễn phí!

Liên hệ: Facebook

Hiện tại, một số thí sinh đạt giải vẫn chưa đến nhận giấy chứng nhận. Trung tâm thông báo nhận lần cuối: chủ nhật ngày 25/9/2022 , thí sinh nào chưa nhận giải và giấy chứng nhận thì đến nhận tại trung tâm. Sau ngày 25/09 nếu thí sinh nào không đến nhận, trung tâm sẽ thu hồi lại giải thưởng và giấy chứng nhận.

Danh sách kết quả:

Solution

Các em hãy theo dõi Fanpage TMATH EDU trên facebook để cập nhật nhiều thông tin từ trung tâm nhé!

TMATH EDU - Nuôi dưỡng đam mê TOÁN TIN!

Thông tin liên hệ:

• Trung tâm: Trung tâm giáo dục Tmath Edu, 9/6 đường Nguyễn Thị Minh Khai, Tp. Vinh, Nghệ An.
• Fanpage: TMATH EDU
• Hotline: 0983420518(Mr Toàn); 0973044327 (Mrs Hiền).

Vào 14h00 ngày mai 5/9/2022, cuộc thi Lập trình thi đấu Nghệ An mở rộng sẽ chính thức diễn ra tại trường THPT Lê Viết Thuật.

Danh sách thí sinh và phiếu dự thi đã được Ban tổ chức hoàn thành, các thí sinh nhận phiếu dự thi tại trung tâm Tmath Edu đến hết ngày hôm nay 4/9/2022.

Ban tổ chức đang gấp rút hoàn thành các khâu chuẩn bị để cuộc thi được diễn ra suôn sẻ nhất.

Chúc các bạn có sự chuẩn bị tốt nhất cho cuộc thi sắp tới.

TMATH EDU - Nuôi dưỡng đam mê TOÁN TIN.

Thông tin liên hệ:

Trung tâm giáo dục Tmath Edu, 9/6 đường Nguyễn Thị Minh Khai, Tp. Vinh, Nghệ An.

TMATH EDU

: 0983420518(thầy Toàn); 0973044327 (cô Hiền).

Nhằm mục đích thúc đẩy phong trào học tập STEM cũng như có những trải nghiệm thú vị về bộ môn tin học và lập trình thi đấu trên địa bàn tỉnh Nghệ An, Trung tâm Tmath Edu cùng các cộng sự tổ chức kỳ thi lập trình thi đấu (Competitive Programming) với tên “Cuộc thi lập trình thi đấu Nghệ An mở rộng” lần thứ nhất.

Chủ trì cuộc thi:

Ông Nguyễn Đức Toàn – trung tâm Tmath Edu.

Ông Trần Thanh Hiệp – chuyên viên Tin học Sở Giáo dục và Đào tạo Nghệ An.

Tham gia cuộc thi, các thí sinh sẽ được:

• Giao lưu học hỏi, kết nối với các học sinh toàn khu vực có cùng đam mê, hứng thú với bộ môn Tin học và lập trình thi đấu.
• Khơi gợi tính sáng tạo trong học tập, rèn luyện của học sinh.
• Phát huy tinh thần học tập năng nổ, làm tiền đề để bước vào năm học mới đầy hứng khởi và hiệu quả.

Hãy đăng kí và tham gia ngay thôi!

️ Đối tượng: Tất cả các bạn học sinh có đam mê với bộ môn Tin học và lập trình thi đấu trong tỉnh Nghệ An và khu vực lân cận, mong muốn được trải nghiệm, giao lưu và học hỏi về Tin học và lập trình thi đấu.

Thời gian và các bước tổ chức:

• Thí sinh đăng ký tham gia từ ngày \(30/08/2022\) đến \(12h\) ngày \(03/09/2022\).
• Thí sinh nhận thẻ dự thi từ \(15h - 17h30\) ngày \(3/9/2022\) tại trung tâm Tmath.
• Ban tổ chức hoàn thành các thủ tục dự thi trước \(18h\) ngày \(4/9/2022\).
• Cuộc thi sẽ chính thức diễn ra vào \(14h\) ngày \(5/9/2022\) tại trường THPT Lê Viết Thuật.
• Chấm thi: \(17h\) ngày \(5/9/2022\).
• Công bố kết quả: \(18h\) ngày \(5/9/2022\).
• Gala tổng kết và trao thưởng: \(19h\) ngày \(5/9/2022\) tại Nhà khách Nghệ An.

LƯU Ý: THÍ SINH TỰ CHUẨN BỊ LAPTOP, SẠC PIN, Ổ CẮM CHUYỀN.

Cơ cấu giải thưởng: Tổng giải thưởng lên đến 20 triệu đồng.

Rất mong chờ sự tham gia tích cực của các bạn trẻ!

TMATH EDU - Nuôi dưỡng đam mê TOÁN TIN!

Mọi ý kiến đóng góp về cuộc thi, phụ huynh và thí sinh có thể liên hệ với BTC tại:

Trung tâm: Trung tâm giáo dục Tmath Edu, 9/6 đường Nguyễn Thị Minh Khai, Tp. Vinh, Nghệ An.

Fanpage: TMATH EDU

Hotline: 0983420518(Mr Toàn); 0973044327 (Mrs Hiền).

Kỳ thi THT tỉnh Nghệ An năm 2021 đã kết thúc. Sau đây là các đề thi để các bạn có thể submit

Bài 1 thi thử - Đếm trứng

Bài 2 thi thử - Dãy cân bằng

Bài 3 thi thử - Quân xe

Bài 4 thi thử - Vi rút

Bài 1 THCS bảng B - Chia bi

Bài 2 THCS bảng B - Xóa số

Bài 3 THCS bảng B - Tô màu

Bài 1 THPT - Thống kê

Bài 2 THPT bảng C - Lũy thừa

Bài 3 THPT bảng C

Bài 4 THPT bảng C - Thí nghiệm với loài kiến