图像压缩问题（动态规划）

图像压缩问题（动态规划） 问题分析：

图像以像素点序列格式存储，即{p1 ,p2 ,…,pn }， 0≤pi≤255，pi在问题中是真正要存储的东西，一般的存储过程是将每个pi都存储在8位二进制中，但对于远小于255的pi来说造成了空间上的浪费，也就是说对于[0,1]内的pi，可以用一位二进制表示；对于[2,3]内的pi，可以用两位二进制表示；对于[8,15]内的pi，可以用四位二进制表示……以此类推。

同时，如果按照这种方法压缩，会产生额外的空间用来存储pi所占的位数，用上边的例子来说，使用一位二进制表示[0,1]内的pi时，额外需要存储的便是1,把这个值记作b[i]。并且，对于{6, 5, 7,5, 245, 180, 28,28,19, 22, 25,20}这样的灰度序列，其中{6，5，7，5}用三位存储，{245，180}八位存储，{28，28，19，22，25，20}用五位存储，我们还需要知道这三个序列的长度用以计算总存储空间。又产生了额外的开销，即每段相同位数存储序列的长度，记作l[i]。（不要把此处的l[i],b[i]中的i跟p[i]中的i搞混，若将原序列分为m段，b[i],l[i]中的i在[1,m]范围内)

动态规划过程：

是否满足最优子结构？

若l[i], b[i]已经是{p1 , p2 , …, pn }的一个最优分段，显然l[1], b[1] 是{p1 ,…,pl[1]}的一个最优分段，l[2], b[2] 是{p1 …,pl[2]+pl[1]}的最优分段……以此类推，满足最优子结构性质

递归结构

代码就不赘述了，从s[0]开始计算，迭代计算即可。