Diophantine Equation and Dynamic Programming

Diophantine Equations (DE) are polynomial equations with only integer solutions, in particular there is the linear Diophantine Equations: https://www.bing.com/search?q=linear%20diophantine%20equation

Related to DE, a nice programming problem is the following: suppose that you're given four numbers {N, A, B, C}, where all these numbers are non-zero positive integers. You can build a DE in the following way:

c1*A + c2*B + c3*C = N

Where the coefficients c1, c2 and c3 are all integers greater than or equal to zero. Now there may exist zero or more solutions to this problem. For example, for {N, A, B, C} = {22, 2, 3, 5}, two solutions would be:

11*2 + 0*3 + 0*5 = 22

1*2 + 0*3 + 4*5 = 22

If you add up the coefficients of the first solution you get 11. The sum of the coefficients for the second solution is 5. What the problem will be asking is the following:

"For all the possible solution to this DE, find the one where the sum of its coefficients is minimized and return that sum"

There is an N^2 brute-force solution which works but for numbers, say, larger than 10^6, such an execution time will be intractable. That's where Dynamic Programming (DP) come handy.

The idea will be to build the solutions for N' = 1....N-1. With that stored somewhere (hence O(N)-space), we can easily find the solution for N using the following formula:

Solution(N) = 1 + Min(Solution(N-A), Solution(N-B), Solution(N-C))

There! Do it by construction (no recursion!) and you'll have an O(3N)-time, O(N)-space solution. Bonus point if you can store the coefficients too. Works super fast, even for large numbers (see result below). Code is down below. Cheers, ACC.

{N,A,B,C} = {314159,2,3,11}

2*2+2*3+28559*11=314159

Sum coefficients = 28563

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _3NumbersSum
{
 class Program
 {
  static void Main(string[] args)
  {
   int n = Int32.Parse(args[0]);
   int[] numbers = { Int32.Parse(args[1]), Int32.Parse(args[2]), Int32.Parse(args[3]) };
   ThreeNumbersSum(n, numbers);
  }

  static int ThreeNumbersSum(int n, int[] numbers)
  {
   NumbersCoefficients[] nc = new NumbersCoefficients[n + 1];

   nc[0] = new NumbersCoefficients();
   for (int i = 1; i <= n; i++)
   {
    nc[i] = new NumbersCoefficients();
    nc[i].total = Int32.MaxValue;
    for (int j = 0; j < numbers.Length; j++)
    {
     if (i - numbers[j] >= 0 && 1 + nc[i - numbers[j]].total < nc[i].total && (i - numbers[j] == 0 || nc[i - numbers[j]].total != Int32.MaxValue))
     {
      nc[i].total = 1 + nc[i - numbers[j]].total;
      nc[i].coefficients[j] = nc[i - numbers[j]].coefficients[j] + 1;
      nc[i].coefficients[(j + 1) % 3] = nc[i - numbers[j]].coefficients[(j + 1) % 3];
      nc[i].coefficients[(j + 2) % 3] = nc[i - numbers[j]].coefficients[(j + 2) % 3];
     }
    }
   }

   if (nc[n].total == Int32.MaxValue) //Edge case if the total is equal to Int32.MaxValue... Oh c'mon, gimme a break!!!!!
   {
    Console.WriteLine("Sorry...");
    return -1;
   }

   for (int i = 0; i < numbers.Length; i++)
   {
    Console.Write("{0}*{1}", nc[n].coefficients[i], numbers[i]);
    if (i < numbers.Length - 1)
    {
     Console.Write("+");
    }
   }
   Console.WriteLine("={0}", n);
   Console.WriteLine("Sum coefficients = {0}", nc[n].total);
   return nc[n].total;
  }
 }

 class NumbersCoefficients
 {
  public int total = 0;
  public int[] coefficients = new int[3];
 }
}