我得到一个输入"N"，我必须找到长度为 N 的列表数，它以 1 开头，这样下一个要添加的数字最多比现在添加的最大数量多 1。例如
N = 3，可能的列表 => （111， 112， 121，122， 123）， [113， 或 131 是不可能的，因为在列表中添加 '3' 时，列表中存在的最大数量将是 '1'，因此我们只能添加 1 或 2]。
N = 4，列表 1213 是可能的，因为当添加 3 时，列表中的最大数字是 '2'，因此可以添加 3。
问题是计算给定输入"N"的此类列表可能的数量。
我的代码是：-
public static void Main(string[] args)
{
var noOfTestCases = Convert.ToInt32(Console.ReadLine());
var listOfOutput = new List<long>();
for (int i = 0; i < noOfTestCases; i++)
{
var requiredSize = Convert.ToInt64(Console.ReadLine());
long result;
const long listCount = 1;
const long listMaxTillNow = 1;
if (requiredSize < 3)
result = requiredSize;
else
{
SeqCount.Add(requiredSize, 0);
AddElementToList(requiredSize, listCount, listMaxTillNow);
result = SeqCount[requiredSize];
}
listOfOutput.Add(result);
}
foreach (var i in listOfOutput)
{
Console.WriteLine(i);
}
}
private static Dictionary<long, long> SeqCount = new Dictionary<long, long>();
private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow)
{
if (listCount == requiredSize)
{
SeqCount[requiredSize] = SeqCount[requiredSize] + 1;
return;
}
var listMaxTillNowNew = listMaxTillNow + 1;
for(var i = listMaxTillNowNew; i > 0; i--)
{
AddElementToList(requiredSize, listCount + 1,
i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow);
}
return;
}
这是蛮力方法。我想知道这个问题的最佳算法是什么？PS ：我只想知道此类列表的数量，因此我确定不需要创建所有列表。（我在代码中的做法）我一点也不擅长算法，所以请原谅这个长问题。
这个问题是动态编程问题的典型示例：
如果将函数 dp（k， m） 定义为长度为 k 且最大数量为 m 的列表数，则具有递归关系：
dp(1, 1) = 1
dp(1, m) = 0, for m > 1
dp(k, m) = dp(k-1, m) * m + dp(k-1, m-1)
实际上，只有一个长度为 1 的列表，其最大元素为 1。当您构建长度为 k 且最大元素为 m 的列表时，您可以获取 max = m 的任何 （k-1）-列表并附加 1 或 2 或 ....或 m。或者，您可以获取最大元素 m-1 的 （k-1） 列表并附加 m。如果您采用最大元素小于 m-1 的 （k-1）列表，那么根据您的规则，您不能通过仅附加一个元素来获得最大 m 值。
您可以使用 O(N^2) 中的动态规划计算所有 k = 1,...,N 和 m = 1,...,N+1 的 dp（k，m），然后您的问题的答案将是
dp(N,1) + dp(N,2) + ... + dp(N,N+1)
因此，该算法O(N^2) 。
有关 C# 中 dp 计算的实现，请参见下文：
int[] arr = new int[N + 2];
for (int m = 1; m < N + 2; m++)
arr[m] = 0;
arr[1] = 1;
int[] newArr = new int[N + 2];
int[] tmp;
for (int k = 1; k < N; k++)
{
for (int m = 1; m < N + 2; m++)
newArr[m] = arr[m] * m + arr[m - 1];
tmp = arr;
arr = newArr;
newArr = tmp;
}
int answer = 0;strong text
for (int m = 1; m < N + 2; m++)
answer += arr[m];
Console.WriteLine("The answer for " + N + " is " + answer);
好吧，今天下午我被一场大火打断了（真的！），但是 FWIW，这是我的贡献：
/*
* Counts the number of possible integer list on langth N, with the
* property that no integer in a list(starting with one) may be more
* than one greater than the greatest integer preceeding it in the list.
*
* I am calling this "Semi-Factorial" since it is somewhat similar to
* the factorial function and its constituent integer combinations.
*/
public int SemiFactorial(int N)
{
int sumCounts = 0;
// get a list of the counts of all valid lists of length N,
//whose maximum integer is listCounts[maxInt].
List<int> listCounts = SemiFactorialCounts(N);
for (int maxInt = 1; maxInt <= N; maxInt++)
{
// Get the number of lists, of length N-1 whose maximum integer
//is (maxInt):
int maxIntCnt = listCounts[maxInt];
// just sum them up
sumCounts += maxIntCnt;
}
return sumCounts;
}
// Returns a list of the counts of all valid lists of length N, and
//whose maximum integer is [i], where [i] is also its index in this
//returned list. (0 is not used).
public List<int> SemiFactorialCounts(int N)
{
List<int> cnts;
if (N == 0)
{
// no valid lists,
cnts = new List<int>();
// (zero isn't used)
cnts.Add(0);
}
else if (N == 1)
{
// the only valid list is {1},
cnts = new List<int>();
// (zero isn't used)
cnts.Add(0);
//so that's one list of length 1
cnts.Add(1);
}
else
{
// start with the maxInt counts of lists whose length is N-1:
cnts = SemiFactorialCounts(N - 1);
// add an entry for (N)
cnts.Add(0);
// (reverse order because we overwrite the list using values
// from the next lower index.)
for (int K = N; K > 0; K--)
{
// The number of lists of length N and maxInt K { SF(N,K) }
// Equals K times # of lists one shorter, but same maxInt,
// Plus, the number of lists one shorter with maxInt-1.
cnts[K] = K * cnts[K] + cnts[K - 1];
}
}
return cnts;
}
与其他人非常相似。 虽然我不会称之为"经典动态编程"，而只是"经典递归"。