● 1049. Trọng lượng của viên đá cuối cùng II
● 494. Tổng mục tiêu
● 474. Một và Zero
Bàn luận chi tiết
1. Trọng lượng của viên đá cuối cùng II
Liên kết LeetCode 1049. Trọng lượng của viên đá cuối cùng II
-
Tư duy
-
Chia viên đá thành hai垛 có tổng trọng lượng gần bằng nhau
-
Vấn đề túi xách 0-1
-
Không nhất thiết phải có hai chiều trọng lượng và giá trị
-
Trong bài này, trọng lượng và giá trị là một
- Ý nghĩa của mảng dp và chỉ số
dp[j] biểu thị tổng trọng lượng có thể chứa được trong túi xách là j, giá trị lớn nhất là dp[j]
- Công thức đệ quy
// Công thức chung cho túi xách 0-1
// weightJ: Trọng lượng của phần tử J; valueJ: Giá trị của phần tử J
dp[j] = max( dp[j], dp[j - weightJ] + valueJ ) // max( không chọn i , chọn i )
// Trong bài này
weightJ := stones[i]
valueJ := stones[i]
dp[j] = max( dp[j], dp[j-weightJ] + valueJ )
- Khởi tạo mảng dp
dp[0] = 0
// Các chỉ số không phải 0: Khởi tạo 0, không thể là số âm
-
Thứ tự duyệt
-
Duyệt các phần tử từ đầu tiên
-
Duyệt túi xách theo thứ tự ngược
-
In mảng
- Giải pháp
func lastStoneWeightII(stones []int) int {
count := len(stones)
sum := 0
for _, stone := range stones {
sum += stone
}
target := sum / 2 // Mục tiêu là tổng giá trị một nửa
dp := make([]int, target+1) // Khởi tạo mảng dp
for i := 0; i < count; i++ { // Duyệt các phần tử
weightI := stones[i] // Trọng lượng của phần tử hiện tại
valueI := stones[i] // Giá trị của phần tử hiện tại
for j := target; j >= weightI; j-- { // Duyệt túi xách theo thứ tự ngược
// Chỉ túi xách có thể tích lớn hơn hoặc bằng trọng lượng của phần tử mới đáng quan tâm
dp[j] = max(dp[j], dp[j-weightI]+valueI) // Cập nhật giá trị của túi xách
}
}
// res:= dp[target] - (sum - dp[target]) // Hiệu giữa hai tổng, lấy trị tuyệt đối
return sum - 2*dp[target]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2. Tổng mục tiêu
Liên kết LeetCode 494. Tổng mục tiêu
Các bạn chú ý hiểu rõ công thức đệ quy: dp[j] += dp[j - nums[i]], công thức này sẽ được sử dụng lại trong các bài sau.
Giải thích video: Lập trình động - Vấn đề túi xách, cách xếp đầy túi xách có bao nhiêu phương pháp? | LeetCode: 494. Tổng mục tiêu_Bilibili
https://programmercarl.com/0494.目标和.html
-
Tư duy
-
Chia thành hai tập
-
Tập thêm: left
-
Tập trừ: right
left - right = target
left + right = sum
left = (sum + target) / 2 // Tổng của tập thêm
right = (sum - target) / 2 // Tổng của tập trừ
// Tìm tất cả các cách xếp để tổng của tập thêm/tập trừ bằng các giá trị tương ứng
- Năm bước của động quy
- Ý nghĩa của mảng dp và chỉ số
dp[j] là số cách để xếp đầy túi xách có thể tích j
- Công thức đệ quy
weightI=nums[i] // Phần tử thứ i
// Hiện tại, túi xách có thể tích weightI, chỉ cần tìm cách xếp để đạt được tổng cần thiết
// Mỗi phần tử chỉ được chọn một lần
dp[j] = dp[j - weightI]
dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]
/* Tương tự như bài toán leo cầu thang */
dp[j] += dp[j - weightI]
- Khởi tạo mảng dp
dp[0] = 1 // Có một cách để xếp túi xách có thể tích 0 (không chọn gì cả)
// Các chỉ số khác đều khởi tạo thành 0
-
Thứ tự duyệt
-
Duyệt các phần tử từ đầu tiên
-
Duyệt túi xách theo thứ tự ngược
-
In mảng
- Giải pháp
func findTargetSumWays(nums []int, target int) int {
sum := 0
for _, num := range nums {
sum += num
}
if sum < abs(target) { // Không thể đạt được tổng bằng cách thêm hoặc trừ
return 0 // Không có lời giải
}
if (sum + target) % 2 != 0 { // Tổng của tập thêm phải là một số nguyên
return 0 // Không tìm thấy tập
}
maxCapacity := (sum + target) / 2
dp := make([]int, maxCapacity + 1)
dp[0] = 1 // Khởi tạo: Có một cách để xếp túi xách có thể tích 0
for i := 0; i < len(nums); i++ {
for j := maxCapacity; j >= nums[i]; j-- {
dp[j] += dp[j - nums[i]]
}
}
return dp[maxCapacity]
}
func abs(a int) int {
return int(math.Abs(float64(a)))
}
3. Một và Zero
Liên kết LeetCode 474. Một và Zero
- Tư duy
- Năm bước của động quy
- Ý nghĩa của mảng dp và chỉ số
dp[i][j] : Tổng số phần tử có thể xếp được khi có i ký tự '0' và j ký tự '1'
- Công thức đệ quy
// x: Số lượng '0' của phần tử hiện tại; y: Số lượng '1' của phần tử hiện tại
dp[i][j] = max( dp[i][j], dp[i-x][j-y] + 1 )
- Khởi tạo mảng dp
dp[0][0] = 0
// Các chỉ số khác đều khởi tạo thành 0
-
Thứ tự duyệt
-
Duyệt các phần tử trước, sau đó duyệt túi xách, túi xách theo thứ tự ngược
-
In mảng
- Giải pháp
func findMaxForm(strs []string, m int, n int) int {
// Khởi tạo mảng dp
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for _, str := range strs {
x, y := countCharacter(str, '0'), countCharacter(str, '1')
// Duyệt túi xách
// i,j có thể đổi chỗ mà không ảnh hưởng đến kết quả
for i := m; i >= x; i-- {
for j := n; j >= y; j-- {
dp[i][j] = max(dp[i][j], dp[i-x][j-y]+1)
}
}
}
return dp[m][n]
}
func countCharacter(str string, char rune) int {
res := 0
for _, c := range str {
if c == char {
res++
}
}
return res
}