算法题

SAY

1、各元素均大于1的正整数列表最少可以划分成几个子列表，划分规则是：1、连续的几个元素可以组成一个子列表，如果首尾元素有大于1的公约数；2、各子列表无重叠部分；3、单独的一个元素可以是一个子列表
    例如（2,3,3,2,3）最少可以划分成2个子列表。（2），（3,3,2,3）或（2,3,3,2），（3）
         （7,11,7,19,7,17,11，19）最少可以划分成2个子列表（7,11,7），（19,7,17,11，19）.



2、一个L*W(均为正整数)的矩形最少可以由多少个正方形(边长为任意正整数)组成？



3、字符串由1~9字符组成，对于任意字符串如何找出所有位置配对（i,j）,使得从i到j位组成的数字是2019的倍数。
    如“1817181712114”，结果（1,5）对应18171，（5,9）对应18171，（9,13）对应12114都是2019的倍数。

epezzaqegazeu

3          2019=3 * 673，对于i-j可以先判断是否3的倍数

ipeuric

2应该很难有很好的算法。
3完全穷举复杂度也不高，对于长度为n的情况，穷举复杂度只用O(n^2)
第一个可以动态规划，在O(n^2)复杂度内完成。
假设我们对于任意k<=m都已经得到前k个元素的最小划分数目f(k),并且设f(0)=0,于是对于第m+1个数可以有伪码

1.    best_len=m+1;   for(i=1; m;i++){         if(gcd(x_i, x_{m+1})>1){               if(f(i-1)+1<best_len){                   best_len=f(i-1)+1;               }         }   }   f(m+1)=best_len;

复制代码