find minimum sum of non-neighbouring K entries inside an array

Given an integer array A of size N, find minimum sum of K non-neighboring entries (entries cant be adjacent to one another, for example, if K was 2, you cant add A[2], A[3] and call it minimum sum, even if it was, because those are adjacent/neighboring to one another), example:

A[] = {355, 46, 203, 140, 28}, k = 2, result would be 74 (46 + 28)

A[] = {9, 4, 0, 9, 14, 7, 1}, k = 3, result would be 10 (9 + 0 + 1)

The problem is somewhat similar to House Robber on leetcode, except instead of finding maximum sum of non-adjacent entries, we are tasked to find the minimum sum and with constraint K entries.

From my prespective, this is clearly a dynamic programming problem, so i tried to break down the problem recursively and implemented something like this:

#include <vector>
#include <iostream>
using namespace std;
int minimal_k(vector<int>& nums, int i, int k)
{
    if (i == 0) return nums[0];
    if (i < 0 || !k) return 0;
    return min(minimal_k(nums, i - 2, k - 1) + nums[i], minimal_k(nums, i - 1, k));
}
int main()
{
    // example above
    vector<int> nums{9, 4, 0, 9, 14, 7, 1};
    cout << minimal_k(nums, nums.size() - 1, 3);
    // output is 4, wrong answer
}

This was my attempt at the solution, I have played around a lot with this but no luck, so what would be a solution to this problem?

This line:

if (i < 0 || !k) return 0;

If k is 0, you should probably return return 0. But if i < 0 or if the effective length of the array is less than k, you probably need to return a VERY LARGE value such that the summed result goes higher than any valid solution.

In my solution, I have the recursion return INT_MAX as a long long when recursing into an invalid subset or when k exceeds the remaining length.

And as with any of these dynamic programming and recursion problems, a cache of results so that you don't repeat the same recursive search will help out a bunch. This will speed things up by several orders of magnitude for very large input sets.

Here's my solution.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// the "cache" is a map from offset to another map
// that tracks k to a final result.
typedef unordered_map<size_t, unordered_map<size_t, long long>> CACHE_MAP;

bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result);
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result);


long long minimal_k_impl(const vector<int>& nums, size_t offset, size_t k, CACHE_MAP& cache)
{
    long long result = INT_MAX;
    size_t len = nums.size();

    if (k == 0)
    {
        return 0;
    }

    if (offset >= len)
    {
        return INT_MAX; // exceeded array boundary, return INT_MAX
    }

    size_t effective_length = len - offset;

    // If we have more k than remaining elements, return INT_MAX to indicate
    // that this recursion is invalid
    // you might be able to reduce to checking (effective_length/2+1 < k)
    if ( (effective_length < k)  ||  ((effective_length == k) && (k != 1)) )
    {
        return INT_MAX;
    }

    if (get_cache_result(cache, offset, k, result))
    {
        return result;
    }

    long long sum1 = nums[offset] + minimal_k_impl(nums, offset + 2, k - 1, cache);
    long long sum2 = minimal_k_impl(nums, offset + 1, k, cache);
    result = std::min(sum1, sum2);

    insert_into_cache(cache, offset, k, result);

    return result;
}

long long minimal_k(const vector<int>& nums, size_t k)
{
    CACHE_MAP cache;
    return minimal_k_impl(nums, 0, k, cache);
}


bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result)
{
    // effectively this code does this:
    // result = cache[offset][k]

    bool ret = false;
    auto itor1 = cache.find(offset);
    if (itor1 != cache.end())
    {
        auto& inner_map = itor1->second;
        auto itor2 = inner_map.find(k);
        if (itor2 != inner_map.end())
        {
            ret = true;
            result = itor2->second;
        }
    }
    return ret;
}

void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result)
{
    cache[offset][k] = result;
}


int main()
{
    vector<int> nums1{ 355, 46, 203, 140, 28 };
    vector<int> nums2{ 9, 4, 0, 9, 14, 7, 1 };
    vector<int> nums3{8,6,7,5,3,0,9,5,5,5,1,2,9,-10};

    long long result = minimal_k(nums1,  2);
    std::cout << result << std::endl;

    result = minimal_k(nums2, 3);
    std::cout << result << std::endl;

    result = minimal_k(nums3, 3);
    std::cout << result << std::endl;


    return 0;
}