图像灰度压缩

⼀幅4*4的图像, 灰度值序列如下.请根据课堂上所讲代码,写出构造解的S数组、l数组和b数组, 追踪解的S数组. 需要体现做题过程,如:每⼀轮i的循环写出内部j循环的前两次和最后两次, 内部循环少于等于四次的需要全部j的计算过程

构造阶段的b数组

一、01背包问题

给定：

• 价值数组 v = {8, 10, 6, 3, 7, 2}
• 重量数组 w = {4, 6, 2, 2, 5, 1}
• 背包容量 c = 12

解决方案分析

1. 二维动态规划

定义 m[i,j]：从前 i 个物品中选择，总体积不超过 j 的最大价值。

• 如果 j < w[i-1]：m[i,j] = m[i-1,j]（不能选择第 i 个物品）
• 否则：m[i,j] = max(m[i-1,j], m[i-1,j-w[i-1]] + v[i-1])（选择或不选择第 i 个物品）

第一题

在构建 c 数组时，不再维护额外的 b 数组来记录方向。 在需要回溯寻找具体的最长公共子序列时，直接通过比较 c[i] [j]、c[i-1] [j] 和 c[i] [j-1] 的值来判断当前字符是否属于最长公共子序列，以及应该向哪个方向回溯。

伪代码

FUNCTION LCS(const string s1, const string s2):
    m = s1.size() // 获取字符串 s1 的长度
    n = s2.size() // 获取字符串 s2 的长度
    dp[m+1][n+1] // 初始化动态规划表
    for i from 1 to m:
        for j from 1 to n: 
            if s1[i-1] == s2[j-1]: // 如果当前字符相同
                dp[i][j] = dp[i-1][j-1] + 1 // 当前位置的 LCS 长度等于左上方的值加 1，表示找到了一个公共子序列字符
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])                 // 如果当前字符不同，当前位置的 LCS 长度取上方和左方的最大值，表示不考虑当前字符
        end for
    end for

    return dp[m][n] // 返回最终的最长公共子序列长度，位于动态规划表的右下角
END FUNCTION

1. binary search

FUNCTION binary_search1(arr[], low, high, x):
    WHILE low <= high:  # 持续搜索直到搜索区间无效
        mid = (low + high) >> 1  # 位运算计算中间索引 (等价于/2但更快)
        
        IF arr[mid] == x:        # 找到目标元素
            PRINT "Found at index " + mid
            RETURE
        ELSE IF arr[mid] < x:    # 目标在右半区
            low = mid + 1        # 调整左边界
        ELSE:                    # 目标在左半区
            high = mid - 1       # 调整右边界
    END WHILE
    PRINT "Element not found"    # 搜索空间耗尽未找到
RETURE

# 时间复杂度 O(log n)，空间复杂度 O(1)

1. 第一章概述：

算法分析： 如何衡量效率（时间/空间复杂度）。

渐近符号 （O，Ω，Θ）用于描述增长速率。

2. 什么是递归？

2.1 调用栈

递归是一种编程技术，其中函数调用自身来解决同一问题的较小实例。它主要涉及两个阶段：

调用： 程序在此处反复调用自身，通常使用逐渐减小或更简单的参数，朝着"终止条件"前进。

返回： 触发"终止条件"后，程序开始从最深层的递归函数返回，逐层汇总每层的结果。递归是一种编程技术，函数通过调用自身来解决同一问题的较小实例。