用动态规划法求解迭代二项式系数的时间复杂度是多少?如何找到它呢?我可以说下面的代码是使用动态规划迭代二项式系数的示例吗?!!
class BinomialCoefficient
{
// Returns value of Binomial Coefficient C(n, k)
static int binomialCoeff(int n, int k)
{
int C[][] = new int[n+1][k+1];
int i, j;
// Calculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}
// A utility function to return minimum of two integers
static int min(int a, int b)
{
return (a<b)? a: b;
}
/* Driver program to test above function*/
public static void main(String args[])
{
int n = 5, k = 2;
System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k));
}
}
发布于 2018-11-10 02:10:27
你填充表的梯形部分(帕斯卡三角形)。空中飞人的高度是k
,长底是n
,短底是n-k
。
因此,它包含k*(n+(n-k))/2
项,算法进行相同数量的单元格操作,并且复杂度为O(nk)
https://stackoverflow.com/questions/53231040
复制相似问题