我正试图用C#动态编程实现 "用不同的方式来表示N与其他数字之和的计数 "问题,我的方法是这样的。
static int howManyWays(int n)
{
int [] safe= new int[n + 1];
// base cases
safe[0] = safe[1] = safe[2] = 1;
safe[3] = 2;
// iterate for all values from 4 to n
for (int i = 4; i <= n; i++)
safe[i] = safe[i - 1] + safe[i - 3]
+ safe[i - 4];
return safe[n];
}
例如,如果我选择 n
作为 n = 4
,那么我的结果是:
4
我想打印出这4个组合的和。
1+1+1+1
1+3
3+1
4
有什么方法可以做到这一点,无论是递归还是使用动态编程? 我的尝试是用递归的方式得到一组组合。
static int[] Combs(int n)
{
int[] tusc = { };
if (n < 0)
yield break;
if (n == 0)
yield return tusc;
int[] X = { 1, 3, 4 };
for(int i = 0; i < X.Length; i++)
{
for(j = 0; j <= Combs(n-X[i]).Length; j++)
{
yield return X + j;
}
}
}
原代码在python中工作,但不知道如何翻译成C#。
def combis(n):
if n < 0:
return
if n == 0:
yield []
for x in (1, 3, 4):
for combi in combis(n-x):
yield [x] + combi
>>> list(combis(5))
[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [1, 4], [3, 1, 1], [4, 1]]
这是一个非常直接的翻译。
using System;
using System.Collections.Generic;
class MainClass
{
static IEnumerable<List<int>> Combs(int n)
{
if (n < 0)
{
yield break;
}
else if (n == 0)
{
yield return new List<int>();
}
foreach (int x in new List<int>() {1, 3, 4})
{
foreach (IEnumerable<int> combi in Combs(n - x))
{
var result = new List<int>() {x};
result.AddRange(combi);
yield return result;
}
}
}
public static void Main(string[] args)
{
foreach (IEnumerable<int> nums in Combs(5))
{
foreach (var i in nums)
{
Console.Write(i + ", ");
}
Console.WriteLine();
}
}
}
输出:
1, 1, 1, 1, 1,
1, 1, 3,
1, 3, 1,
1, 4,
3, 1, 1,
4, 1,
备注。
yield
,改变 Combs
头,以返回一个 IEnumerable<int>
而非 int[]
.List.AddRange
来翻译 +
来自Python的列表连接操作。X
. 在Python版本中。x
中的一个元素。{1, 3, 4}
选项列表,但在C#版本中,它是整个数组。Combs(n-X[i]).Length
这样做是没有意义的--它调用了 Combs
,取结果的长度,然后把所有的结果都扔掉,所以它就像一个非常昂贵的计数器。j
给你一个计数器的索引,而不是子函数中的一个元素。Combs
的调用。foreach
是对Python的 for .. in
循环。{1, 3, 4}
列表可能应该做成一个参数,允许调用者控制其行为。