算法分析习题选讲(第六章) 李承乾 498727460@ 第六章? 1011 Lenny's Lucky Lotto ? 1121 Tri Tiling ? 1264 Atomic Car Race ? 1828 Minimal ? 1527 Tiling a Grid With Dominoes ? 1148 过河? 1176 Two Ends ? 1163 Tour ? 1345 能量项链? 1687 Permutation 1011 Lenny's Lucky Lotto ?给出 N和M,问有多少个长度为 N的序列, 使得每个数的范围都在[1,M] 之间,并且序列中每一个数至少是前一个数的两倍。解题思路? dp[i][j] 表示考虑前 i位且第 i位为 j的方案。?先枚举位数 i,再枚举最后一个数 j,最后统计 k。?时间复杂度 O(N *M* M) 。 1121 Tri Tiling ?用1*2的长方形铺满 3*n的长方形,有多少种方法。解题思路?定义如图几种缺口状态。 012345状态转移 0 -> 5 1 -> 3 2 -> 4 3 -> 5 2 -> 5 5 -> 3 5 -> 2 5 -> 0 4 -> 2 3 -> 5 初始第 0列是状态 0终止第 n+1 列是状态 5
算法分析习题课 第六章 李承乾 来自淘豆网m.daumloan.com转载请标明出处.
