coinchange.cs

using System;
using System.Collections.Generic;
using System.IO;
class Program 
{
    static long Solve(int n, int m, int[] c)
	{
        long[,] C = new long[n + 1, m];
        
        for (var i = 0; i <= n; i++)
		{
            for (var j = 0; j < m; j++)
			{
                if (i == 0) C[i, j] = 1;
                else 
				{
                    var includingCj = (i - c[j] >= 0)? C[i - c[j], j] : 0;
                    var notIncludingCj = (j > 0) ? C[i, j - 1] : 0;
                    
                    C[i, j] = includingCj + notIncludingCj;
                }
            }
        }
        
        return C[n, m - 1];
    }
    
    static void Main(String[] args) 
	{
        var l = Console.ReadLine();
        var n = Convert.ToInt32(l.Split(' ')[0]);
        var m = Convert.ToInt32(l.Split(' ')[1]);
        l = Console.ReadLine();
        var arr = l.Split(' ');
        int[] c = new int[m];
        for (var i = 0; i < m; i++)
            c[i] = Convert.ToInt32(arr[i]);
        
        var r = Solve(n, m, c);
        Console.WriteLine(r);
    }
}