给定四个大小相等的数组n，我可以用多少种方法选择每个数组中一个和为k的元素

Question

如果我有四个大小相同的数组，我如何确定从每个数组中选择一个元素的方法数量，以使四个元素具有相同的和？

例如，有81种方法可以从每个和为4的数组中选择一个元素。

A. 1 1 1 
B. 1 1 1 
C. 1 1 1 
D. 1 1 1 

我不知道如何做到这一点，如果没有某种野蛮的强迫。

Answer 1

想法

1. 从1数组中获取和k的方法数=k在数组中的出现次数
2. 从2个数组中获得和k的方式数=sum(count(k-x) for each element x in array 2)，其中count(y)是从第一个数组中获取和y的方式数。如果将第1点的结果记忆起来，则可以在O(1)中获得count(y)
3. 从3个数组中获得和k的方式数=sum(count(k-x) for each element x in array 3)，其中count(y)是从前两个数组中获取和y的方式数。同样，如果您将第2点的结果记忆起来，则可以在O(1)中获得count(y)

您现在应该已经了解了这个概念；从n阵列获得和k的方式的数目＝sum(count(k-x) for each element x in the nth array)，其中count(y)是从第一个n-1阵列获得和的y的方式的数量。

动态编程

您需要构建一个记忆表，它基本上告诉您从第一个y数组中获取和x的方法的数量。如果您有第一个n-1数组的此表，则可以有效地计算包括n-th数组在内的所有和，并更新该表。