[Hackerearth] WarFire

 

Problem Link    : WarFire 
Category        : Dynamic Programing
Contest         : DSA Coding Contest - January '24

#include<bits/stdc++.h>
using namespace std;
int solve (int n, vector<int> arr) {
        vector<int> powers = arr;
        int sum = accumulate(powers.begin(), powers.end(), 0ll);
        vector<vector<int>> dp(n, vector<int>(sum + 1, -1));
        const int INF = 1LL << 60;
        function<int(int, int)> Solve = [&](int pos, int cursum) {
            if (pos >= n) {
                return abs(sum - 2 * cursum);
            }
            int &ret = dp[pos][cursum];
            if (~ret) {
                return ret;
            }
            int take = Solve(pos + 1, cursum + powers[pos]);
            int skip = Solve(pos + 1, cursum);
            return ret = min(take, skip);
        };
        return Solve(0, 0);
}
 
int main() {
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i = 0; t_i < T; t_i++)
    {
        int N;
        cin >> N;
        vector<int> arr(N);
        for(int i_arr = 0; i_arr < N; i_arr++)
        {
        	cin >> arr[i_arr];
        }
 
        int out_;
        out_ = solve(N, arr);
        cout << out_;
        cout << "\n";
    }
}