Cách chuyển đổi giải pháp đệ quy sang lập trình động (3D-DP)

[ad_1]

Hôm qua tôi đã gặp những điều sau đây câu hỏi trong một cuộc thi:

Báo cáo vấn đề:

Bạn được cấp một mảng ‘A’ gồm các số nguyên ‘N’ được đánh số từ ‘0’ đến ‘N – 1’ và một số nguyên ‘K’. Bạn phải xác định số lượng các chuỗi con có độ dài lớn hơn ‘1’ và tổng các phần tử liên tiếp chia hết cho ‘K’.

Dãy con là một mảng có thể được lấy từ mảng ban đầu bằng cách xóa một số phần tử mà không thay đổi thứ tự của các phần tử còn lại.

Nhiệm vụ của bạn là cho biết số dãy con có độ dài lớn hơn ‘1’ và tổng các phần tử liên tiếp chia hết cho ‘K’. Vì câu trả lời có thể rất lớn nên trả về theo modulo ’10^9 + 7′.

Hạn chế:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <= 'Một[i]' <= 10^9
Giới hạn thời gian: 1 giây

Những gì tôi đã thử:

Mã của tôi:

int mod = 1e9+7;
long long solve(vector <int> &a,int k,int i,int l,int last){
    if(i==0){
        if(l>1) return 1;
        else return 0;
    }
    else{
        if(last==-1 || ((a[last-1]+a[i-1])%k==0)){
            return(solve(a,k,i-1,l+1,i)%mod + solve(a,k,i-1,l,last)%mod)%mod;
        }else{
            return solve(a,k,i-1,l,last)%mod;
        }
    }
}
long long kDivsibleSubsequences(int n, int k, vector <int> &a){
    return solve(a,k,n,0,-1)%mod;
}

l = độ dài của dãy con hiện tại.
cuối cùng = phần tử cuối cùng mà chúng tôi đã chọn từ vectơ

Tôi đã nghĩ đến một giải pháp đệ quy với tính năng ghi nhớ để tối ưu hóa hơn nữa, nhưng sau khi viết mã, tôi bị mắc kẹt với 3 biến thay đổi (i, l, cuối cùng) trong đệ quy, nghĩa là không thể thực hiện được dp 3-D do hạn chế.

Vì tôi là người mới bắt đầu học DP nên việc trực tiếp áp dụng phương pháp tiếp cận từ dưới lên là không khả thi đối với tôi trong thời gian ngắn như vậy, ai đó có thể vui lòng cho tôi biết liệu có cách nào để ghi nhớ những câu hỏi như vậy không hay tôi sẽ phải đến bằng giải pháp từ dưới lên.

Tái bút- Cảm ơn trước 🙂

[ad_2]