mấy bác giỏi thuật toán cho em hỏi bài này

amolad said:

Qui hoạch động thôi:
gọi Dp[k,i], là tổng lớn nhất, tạo được từ k số với số cuối ở vị trí i.
Theo vd trên:

-> Dp[1] = [4, 7, 6, 4, 6, 9, 9 , 4]
Dp[2] = [x, x, 10, 11, 13, 16, 16, 13] (2 giá trị đầu không có vì không thể tính được, không đủ 2 số không liên tục)
Dp[3] = [x, x, x, x, 16, 20, 22, 20] (không thể tạo được 3 số ko liền kề nhau từ 4 phần tử đầu)

-> kq = 22

Code:

-> công thức: dp[k,i] = A[i] + max(dp[k - 1][0] ... dp[k - 1][i - 2])

lặp 3 lần qua mảng rồi tính. -> O(n)

Click to expand...

sincos90 said:

Cho hỏi bài toán này nó ứng dụng vào việc gì thế?

Click to expand...

afatnan said:

Giống bác ở trên, nhưng cần thêm testcase

Python:

import math
import copy
a = [4, 7, 6, 4, 6, 9, 9, 4]
b = copy.copy(a) # b[i] is a[i] + max(a[..i-2])
mn = a[0]
for i in range(2, len(a)):
    b[i] += mn
    mn = max(mn, a[i - 1])
mx = -math.inf
for i in range(4, len(a)):
    mx = max(mx, a[i] + b[i - 2])
print(mx)

Click to expand...

fun solution(A: IntArray) {
    val n = A.size
    val dp = Array(n) { IntArray(n) }
    dp[1] = A
    for(k in 2..3) {
        for (i in 0..n - 1) {
            val dp1 = (0..i - 2).map {
                dp[k-1][it]
            }.maxOrNull()
            if (dp1 == null) {
                dp[k][i] = Int.MIN_VALUE
            } else {
                dp[k][i] = A[i] + dp1
            }
        }
    }
   
    return dp[3].max()
}

solana123 said:

em implement step by step của bác @amolad bằng kotlin thấy chạy đúng rồi, chứ em đọc đi đọc lại implement của bác em ko hiểu, mặc dù em run thử thì thấy cũng ra KQ đúng

Java:

fun solution(A: IntArray) {
    val n = A.size
    val dp = Array(n) { IntArray(n) }
    dp[1] = A
    for(k in 2..3) {
        for (i in 0..n - 1) {
            val dp1 = (0..i - 2).map {
                dp[k-1][it]
            }.maxOrNull()
            if (dp1 == null) {
                dp[k][i] = Int.MIN_VALUE
            } else {
                dp[k][i] = A[i] + dp1
            }
        }
    }
 
    return dp[3].max()
}

Click to expand...

amolad said:

cái implementation này nó là O(n^2).

còn của bác kia thì store cái max luôn, đỡ phải loop lại mỗi bước nên là O(n).

Click to expand...

-> công thức: dp[k,i] = A[i] + max(dp[k - 1][0] ... dp[k - 1][i - 2])

solana123 said:

à ok, nhưng quả thực nó rất khó với em để hiểu. Sẵn bác cho hỏi làm sao để rút ra công thức cho mấy bài dạng DP này vậy, ví dụ bài này:

Code:

-> công thức: dp[k,i] = A[i] + max(dp[k - 1][0] ... dp[k - 1][i - 2])

Click to expand...

solana123 said:

Em đang gặp bài toán tìm 3 số có tổng lớn nhất trong mảng mà bất kì số nào trong 3 số cũng ko đc liền kề nhau. Ví dụ: A = [4, 7, 6, 4, 6, 9, 9, 4] thì output sẽ là 3 số A[1] = 7, A[4] = 6 và A[6] = 9. Tổng 3 số này là: 7 + 6 + 9 = 22

Lúc đầu em định giải nó theo quy hoạch động giống tìm tổng tất cả các số lớn nhất không liền kề nhau trong mảng nhưng không áp dụng được trong trường hợp này.

Click to expand...

freedom.9 said:

Sao ko giải bằng dynamic programming được, bài này chắc chỉ cần 2 states là ok rồi

via theNEXTvoz for iPhone

Click to expand...

solana123 said:

tại gà đó fen, giờ mới đc khai sáng

Click to expand...

solana123 said:

Em đang gặp bài toán tìm 3 số có tổng lớn nhất trong mảng mà bất kì số nào trong 3 số cũng ko đc liền kề nhau. Ví dụ: A = [4, 7, 6, 4, 6, 9, 9, 4] thì output sẽ là 3 số A[1] = 7, A[4] = 6 và A[6] = 9. Tổng 3 số này là: 7 + 6 + 9 = 22

Lúc đầu em định giải nó theo quy hoạch động giống tìm tổng tất cả các số lớn nhất không liền kề nhau trong mảng nhưng không áp dụng được trong trường hợp này.

Click to expand...

_Gia_Cat_Luong_ said:

Hmm, tự dưng thấy bài này chưa chắc cần DP. How about greedy zip value với index, xong sort lại mảng rồi pick từ phần tử lớn nhất xuống, nếu index gần nhau thì... skip qua pick phần tử nhỏ t4 t5 gì đó là được ?

Ngẫm lại thì bài toán này chỉ cần work trên 5 phần tử lớn nhất, chắc chắn sẽ có cách chọn ra 3 phần tử không nằm sát nhau ở trong đó.

Click to expand...

freedom.9 said:

Ủa bài này kết quả 25 mà nhỉ?
4 + 6 + 6 + 9 mới đúng chứ sao lại 22
À cách giải của mình do mình đọc lộn đề tưởng là tìm dãy số có tổng lớn nhất ko liền kề nhau. Tìm tổng 3 số thôi thì mình nghĩ chỉ cần làm greedy thôi chứ cũng đâu cần dynamic programming ta.

Mình cũng nghĩ có cách greedy, nhưng mà ko phải sort vì sort lại sẽ mất đi cái index liền kề.

Click to expand...

public class Solution
{
    public long findMax(int[] nums)
    {
        var maxLefts = new int[nums.Length];
        var maxRights = new int[nums.Length];
        int maxSofar = int.MinValue;
        for (int i = 0; i < nums.Length - 2; i++)
        {
            maxSofar = Math.Max(maxSofar, nums[i]);
            maxLefts[i + 2] = maxSofar;
        }

        maxSofar = int.MinValue;
        for (int i = nums.Length - 1; i >= 2; i--)
        {
            maxSofar = Math.Max(maxSofar, nums[i]);
            maxRights[i - 2] = maxSofar;
        }

        long ans = int.MinValue;
        for(int i = 2; i < nums.Length - 2; i++)
        {
            ans = Math.Max(ans, nums[i] + maxLefts[i] + maxRights[i]);
        }

        return ans;
    }
}

_Gia_Cat_Luong_ said:

Thì zip với cái index luôn trước khi sort. Kiểu:

[4, 7, 6, 4, 6, 9, 9, 4]
Zip => [(4, 0), (7, 1), (6, 2), (4, 3), (6, 4), (9, 5), (9, 6), (4, 7)]
Sort => [(4, 0), (4, 3), (4, 7), (6, 2), (6, 4), (7, 1), (9, 5), (9, 6)]
Select lấy 3 từ cuối mảng về, nếu index gần nhau thì skip:
(9, 6) => ok
(9, 5) => skip
(7, 1) => ok
(6, 4) => ok

Click to expand...