0016算法笔记——【动态规划】图像压缩问题

0016 算法笔记——【动态规划】图像压缩问题 1 1、问题描述：、问题描述： 在计算机中，常用像素点的灰度值序列{p1,p1,……p n}表示图像。其 中整数 pi,10) 64. { 65. k++; 66. i=i/2; 67. } 68.returnreturn k; 69. } 70. 71. voidvoid Traceback(intint n,intint 75. Traceback(n-l[n],i,s,l); 76. s[i++]=n-l[n];//重新为 s[]数组赋值，用来存储分段位置 77. } 78. 79. voidvoid Output(intint s[],intint l[],intint b[],intint n) 80. { 81.//在输出 s[n]存储位数后，s[]数组则被重新赋值，用来存储分段的位置 82. cout“图像压缩后的最小空间为：“s[n]endl; 83.intint m = 0; 84. Traceback(n,m,s,l); 85. s[m] = n; 86. cout“将原灰度序列分成“m“段序列段“endl; 87.forfor(intint j=1; j=m; j++) 88. { 89. l[j] = l[s[j]]; 90. b[j] = b[s[j]]; 91. } 92.forfor(intint j=1; j=m; j++) 93. { 94. cout“段长度：“l[j]“,所需存储位数:“b[j]endl; 95. } 96. } 算法 Compress 只需 O(n)空间。由于在算法 Compress 中 j 的循环 次数不超过 256,故对每一个确定的 i 可在 O(1)时间内完成。因此整个 算法的时间复杂度为 O(n)。算法 Compress 的执行过程可以下图表 示： 方法 Output 中，在输出 s[n]的最小存储空间后，s[]数组被重新赋 值，用来存储分段的位置，一边回溯构造最优解。程序运行结果如 下：