Dynamic programming technique

Question

I have this problem that I'm trying to solve:

Given two numbers K and S, determine how many different values of X, Y, and Z exist such that 0 ≤ X, Y, Z ≤ K and X + Y + Z = S.

Now, what I did is a recursive solution that tries every possible value for each one of the three digits.

int count_sum(int k,int s,int sum=0,int limit=1,int counter=0)
{
    if(sum>s)
        return 0;

    if(sum==s)
        return 1;

    if(limit>3)
        return 0;

    for(int i=0; i<=k; i++)
    {
        if(i>s)
            break;
        counter=counter + count_sum(k,s,sum+i,limit+1);
    }
    return counter;
}

I know that this is O(k^3), which is too high. I also know that there is a hack to solve this problem in O(k^2). However, what I'm trying to do is optimize this solution with the technique of dynamic programming. I have tried to sketch a tree, but I couldn't figure out how to optimize it.

Answer 1

Well, as long as there are only triplets, here's an O(k) solution:

#include <iostream>
#include <algorithm>
using namespace std;

int countTriples( int k, int S )
{
   int result = 0;
   for ( int Z = max( S - 2 * k, 0 ); Z <= min( k, S ); Z++ ) result += min( k, S - Z ) - max( S - Z - k, 0 ) + 1;
   return result;
}

int main()
{
   int k, S;
   cout << "Enter k and S: ";   cin >> k >> S;
   cout << countTriples( k, S );
}

Some output:

Enter k and S: 3 5
12

corresponding to collection

2 3 0
3 2 0

1 3 1
2 2 1
3 1 1

0 3 2
1 2 2
2 1 2
3 0 2

0 2 3
1 1 3
2 0 3

EDIT: Generalisation

You should be able to generalise this (by recursion) to n-tuples such that

0<=X1,X2,...,Xn<=k and X1+X2+...+Xn=S

The method is O(k^(n-2)) since the base cases n=1 and n=2 are O(1).

#include <iostream>
#include <algorithm>
using namespace std;

int countTuples( int k, int S, int n )
{
   if      ( n == 1 ) return ( k >= S );
   else if ( n == 2 ) return 2 * k >= S ? min( k, S ) - max( S - k, 0 ) + 1 : 0;

   int result = 0;
   for ( int X = max( S - (n-1) * k, 0 ); X <= min( k, S ); X++ ) result += countTuples( k, S - X, n - 1 );
   return result;
}

int main()
{
   int k, S, n;
   cout << "Enter k, S, n: ";   cin >> k >> S >> n;
   cout << countTuples( k, S, n );
}

Output:

Enter k, S, n: 3 5 3
12

Answer 2

Here is an O(1) solution, but this is not using dynamic programming. This simply uses a mathematical formula to directly compute the number of valid solutions in O(1) time

#include <iostream>
using namespace std;

int C(int n, int k) {
    if (k > n) return 0;
    int result = 1;
    for (int i = 1; i <= k; i++) {
        result *= n - i + 1;
        result /= i;
    }
    return result;
}

int count_sum(int K, int S) {
    if (S > 3*K) return 0;
    int result = C(S+2, 2);
    result -= 3 * C(S-K-1, 2);
    result += 3 * C(S-2*K-2, 2);
    result -= C(S-3*K-3, 2);
    return result;
}

int main() {
    int K=10, S=15;
    //cin >> K >> S;
    cout << count_sum(K, S) << endl;
    return 0;
}

Now using dynamic programming, I think the best approach will be limited only to O(K^3). Unless there are only triplets as stated by lastchance then you can have an O(k).

Using dynamic programming with O(K^3) time where its running time grows cubically with the size of the input:

#include <iostream>
#include <vector>
using namespace std;

int count_sum(int K, int S, int n, vector<vector<vector<int>>>& dp) {
    if (n == 1) return (K == S);
    if (dp[n][K][S] != -1) return dp[n][K][S];
    int result = 0;
    for (int X = max(S - (n-1) * K, 0); X <= min(K, S); X++) {
        result += count_sum(K, S - X, n - 1, dp);
    }
    dp[n][K][S] = result;
    return result;
}

int main() {
    int K = 10, S = 15, n = 3;
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(K+1, vector<int>(S+1, -1)));
    cout << count_sum(K, S, n, dp) << endl;
    return 0;
}