Bài toán Nguồn: Codewars Đọc hiểu Số Hamming là một số dương có dạng $2^ỉ3^j5^k$ với $i, j, k$ là các số không âm. Viết chương trình tính số Hamming nhỏ nhất thứ n. Đặc biệt: Số Hamming đầu tiên là $1 = 2^03^05^0$ Số Hamming thứ hai là $2 = 2^13^05^0$ Số Hamming thứ ba là $3 = 2^03^15^0$ Số Hamming thứ tư là $4 = 2^23^05^0$ Số Hamming thứ năm là $5 = 2^03^05^1$ 20 số Hamming nhỏ nhất đầu tiên được đưa vào trong test mẫu....
Bài toán Nguồn: Tiếng Việt: Codeforces - Bản dễ Có thể giải với $O(n^2)$ Codeforces - Bản khó Cần giải bằng $O(n\log n)$ Tiếng Anh: Leetcode Cho một dãy số nguyên nums. Tìm độ dài của dãy con tăng đơn điệu dài nhất. Biết rằng dãy con tăng đơn điệu là 1 dãy $a_1,..,a_k$ thỏa mãn $$ \begin{align} &i_1 < i_2 < \dots < i_k,\\\ &nums[i_1] < nums[i_2] < \dots < nums[i_k] \end{align} $$ Ví dụ:...
Bài toán Nguồn: Codewars Đọc hiểu Theo Wikipedia : Bài toán xâu con chung dài nhất là bài toán tìm một xâu có độ dài lớn nhất và là xâu con của mọi xâu trong một tập hợp các xâu. Khác với chuỗi con, các phần tử của xâu con không nhất thiết phải liên tiếp nhau. Với 2 chuỗi được nhập vào, nhiệm vụ của bạn chính là tìm ra xâu con dài nhất của chúng....
Bài toán Nguồn: Codewars Đọc hiểu Có bao nhiêu cách phân tích số n thành tổng các số? Theo wikipedia: https://vi.wikipedia.org/wiki/Phân_hoạch_(lý_thuyết_số) Trong số học, sự phân tích một số nguyên dương n là cách viết số đó dưới dạng tổng của các số nguyên dương. Hai cách phân tích có các số hạng giống nhau được coi là một cách phân tích. Ví dụ: Input: 4 Output: 5 //4, 3+1, 2+2, 2+1+1, 1+1+1+1 Lời giải Bài toàn này có thể dùng phương pháp liệt kê để đếm nhưng mà như vậy rất là chậm khi $n$ là số lớn nên mình sẽ dùng quy hoạch động (Oω<)☆....
Bài toán Nguồn: Codeforces Đọc hiểu Tìm phần dư của số Fibonacci thứ $n$ ($n <= 10^{18}$) cho $10^9 + 7$. Như vậy, mình cần tìm $F_n$ trong dãy số được định nghĩa: $$ \begin{aligned} F_0 & = 0\\ F_1 & = 1\\ F_i & = F_{i-1} + F_{i-2} (i >= 2) \end{aligned} $$ Ví dụ: Input: 50 Output: 586268941 Lời giải Cách 1: Quy hoạch động Xem phương trình sai phân của dãy fibonacci là công thức truy hồi, mình có thể viết thành đoạn code sau:...
Bài toán Nguồn: Leetcode , Codewars Đọc hiểu: Bạn có một lượng đồng xu với các mệnh giá khác nhau và một tổng số tiền amount. Nhiệm vụ của bạn là tính xem có bao nhiêu cách khác nhau để đổi được số tiền với số xu đã cho. Số lượng xu không giới hạn. Ví dụ: Input: amount = 5, coins = {1,2,5} Output: 4 //{5, 2+2+1, 2+1+1+1, 1+1+1+1+1} Lời giải Với bài này mình sẽ lần lượt đi qua các giai đoạn của nó mà ở mỗi gia đoạn số xu của mình sẽ thay đổi dẫn đến sự thay đổi của kết quả bài toán....
Bài toán Nguồn: Leetcode Đọc hiểu Bạn có một lượng đồng xu có các mệnh giá khác nhau và tổng số tiền amount. Nhiệm vụ của bạn là tìm số xu ít cần ít nhất để tạo nên số tiền đó (không giới hạn số đồng xu). Nếu số tiền đó không thể tạo thành thì trả về -1. Ví dụ: Input: coins = {1,2,5}, amount = 11 Output: 3 //2 đồng 5 và 1 đồng 1 Input: coins = {2}, amount = 3 Output: -1 Lời giải Cách 1: Vét cạn bằng đệ qui Lấy ví dụ như trên, mình có amount là 11....
Bài toán: Nguồn: Codewars.com Cho một dãy gồm n số nguyên $a_1, a_2,…, a_n$. Hãy tìm một đoạn con (dãy gồm các phần tử liên tiếp nhau) có tổng lớn nhất. Input: {-2, 1, -3, 4, -1, 2, 1, -5, 4} Output: 6 //vì đoạn con có tổng lớn nhất là {4, -1, 2, 1} Trường hợp đơn giản nhất là mảng chỉ có số dương, khi đó kết quả chính là tổng tất cả các số trong mảng....