给定n层数字三角形，动态规划计算的时间为O（n^3）

数字三角形

状态转移方程是状态间的递推关系，也是子问题间的递推关系。状态变量取值不同对应不同问题状态，也对应不同子问题。

0-1背包问题的动态规划算法的时间复杂度是Q(n W)，是多项式时间算法.

动态规划算法的计算矩阵连乘问题的时间为O（）

A、nlogn

B、n(logn)^2

C、n^2

D、n^3

恰好装满的0-1背包问题，初始化时除了M[0]为0，其它M[1..C]均设为-∞，可以保证最终得到的M[C]是一种恰好装满背包的最优解。

区间动归使用链长，先计算小区间，再递增计算大区间。

动态规划计算最长不降子序列的时间是O（）

A、n^3

B、n^2

C、nlogn

D、n^2logn

矩阵连乘的计算次序可以用完全加括号的方式来确定。

拓扑排序的时间复杂度是O( )

A、n^3

B、n^2

C、mn

D、m+n

矩阵连乘问题的不同子问题个数为 O（n^2）