[关闭]
@Pigmon 2016-04-29T06:14:06.000000Z 字数 3442 阅读 166

算法作业6袁胜_2016M8009073008

Python


基本思路

采用自底向上的动态规划法。

伪码

  1. Algorithm Domino(s[]):
  2. n <- Length(s);
  3. Ends0 <- 0;
  4. Ends1 <- 0;
  5. Stat0 <- '0'; #Ends0的组合序列字符串
  6. Stat1 <- '1'; #Ends1的组合序列字符串
  7. for (i in 0..n-2):
  8. f00 <- s[i]与s[i+1]在组合00的情况下的R[i]*L[i+1];
  9. f01 <- s[i]与s[i+1]在组合01的情况下的R[i]*L[i+1];
  10. f10 <- s[i]与s[i+1]在组合10的情况下的R[i]*L[i+1];
  11. f11 <- s[i]与s[i+1]在组合11的情况下的R[i]*L[i+1];
  12. Sum00 <- Ends0 + f00;
  13. Stat00 <- Stat0 连接 '0';
  14. Sum01 <- Ends0 + f01;
  15. Stat01 <- Stat0 连接 '1';
  16. Sum10 <- Ends1 + f10;
  17. Stat10 <- Stat1 连接 '0';
  18. Sum11 <- Ends1 + f11;
  19. Stat11 <- Stat1 连接 '1';
  20. Ends0 <- Max(Sum00, Sum10); 记录 Stat0;
  21. Ends1 <- Max(Sum01, Sum11); 记录 Stat1;
  22. end
  23. return Max(Ends0, Ends1);

时间复杂度分析

对于所有 骨牌,每次循环需要计算:
- 的00, 01, 10, 11四种组合的 的值。
- 将00, 01两个组合计算的结果与 Ends0 相加得(Sum00, Sum01);
- 将10, 11两个组合计算的结果与 Ends1 相加得(Sum10, Sum11);
- 将 Max(Sum00, Sum10)记录到 Ends0;
- 将 Max(Sum01, Sum11)记录到 Ends1;

以上计算的时间复杂度为常数级O(C)。
循环一共执行 n-1 次。
,即时间复杂度为,复合题目要求。

计算过程

以题目中的骨牌序列为例。

step1

计算 s1,s2 两张骨牌在00, 01, 10, 11四种组合下的



在以0结尾的组合中,f00较大,遂舍弃f10,Ends0=f00=16
在以1结尾的组合中,f01较大,遂舍弃f11,Ends1=f01=32

Ends0序列为00
Ends1序列为01

step2

计算 s2,s3 两张骨牌在00, 01, 10, 11四种组合下的







Ends0序列为010
Ends1序列为001

step3

计算 s3,s4 两张骨牌在00, 01, 10, 11四种组合下的







Ends0序列为0100
Ends1序列为0101

step4

计算 s4,s5 两张骨牌在00, 01, 10, 11四种组合下的







Ends0序列为01000 (选第1个)
Ends1序列为01011 (选第1个)

step5

计算 s5,s6 两张骨牌在00, 01, 10, 11四种组合下的







添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注