C语言动态规划入门：线性DP四大经典模型解析

数字三角形：基础状态转移

数字三角形是理解动态规划边界处理的经典入门题。目标是求从顶端到底端的最大路径和。

第1步：问题分析与状态表示

将三角形视为一个二维数组 a[i][j]，其中 i 为层数，j 为该层的位置。定义 f[i][j] 为到达位置 (i, j) 时的最大路径和。

观察图形可知，到达点 (i, j) 只能从其上一层的两个相邻点转移而来：左上方的 (i-1, j-1) 或正上方的 (i-1, j)（注意坐标系对齐方式）。因此状态转移的核心在于取这两者中的最大值并加上当前点的值。

第2步：边界处理与初始化

由于三角形边缘的节点只有一条路径来源，直接套用公式会导致越界。常见的做法是将所有 f[i][j] 初始化为负无穷（-INF），然后将起点 f[1][1] 设置为 a[1][1]。这样在计算时，非法来源的负无穷不会影响最终的最大值比较。

第3步：C语言代码实现

代码需注意数组下标从1开始以简化逻辑，且需遍历所有最后一层的节点找出全局最大值。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    // 读取输入数据
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);

    // 初始化所有状态为负无穷
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;

    // 设置起点
    f[1][1] = a[1][1];

    // 状态转移：从第2层开始递推
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    // 寻找最后一层的最大值
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}

最长上升子序列（LIS）：从 O(n²) 到 O(nlogn)

给定一个无序序列，求其最长的严格递增子序列长度。这是线性DP中最著名的应用之一。

第1步：基础解法 O(n²) 思路

定义 f[i] 为以 w[i] 结尾的最长上升子序列的长度。

• 初始状态： 每个元素至少可以独立构成一个长度为1的子序列，故 f[i] = 1。
• 状态转移： 遍历 i 之前的所有 j。如果 w[i] > w[j]，说明可以将 w[i] 接在以 w[j] 结尾的子序列之后，此时更新 f[i] = max(f[i], f[j] + 1)。

这种方法需要两层循环，时间复杂度为 O(n²)，适用于小规模数据。

#include <iostream>

using namespace std;

const int N = 1010;

int n;
int w[N], f[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> w[i];

    int mx = 1;
    // 枚举每一个位置作为结尾
    for (int i = 0; i < n; i++) {
        f[i] = 1; // 初始长度为1
        // 查找前面所有能形成上升序列的前驱节点
        for (int j = 0; j < i; j++) {
            if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);
        }
        mx = max(mx, f[i]); // 记录全局最大值
    }

    cout << mx << endl;
    return 0;
}

第2步：优化解法 O(nlogn) 思路

当数据规模较大时（如 n > 10^5），O(n²) 会超时。我们需要利用 f[] 数组的单调性进行优化。

重新定义状态： 令 f[len] 表示长度为 len 的所有上升子序列中，末尾元素的最小值。

• 显然，f[len] 是严格单调递增的。因为如果存在长度更长的子序列其末尾元素反而更小，那么更短长度的子序列完全可以替换它，这与“最小值”的定义矛盾。
• 由于单调性，我们可以使用二分查找来快速定位位置。

操作逻辑： 对于新来的数字 w[i]：w[i] 大于当前最长子序列的末尾元素（即 w[i] > f[cnt-1]），则可以直接延长最长子序列，长度 cnt+1。f[] 数组中二分查找第一个大于等于 w[i] 的位置 k，并用 w[i] 更新 f[k]。这意味着我们找到了一个长度为 k 的子序列，其末尾元素比之前记录的更小，从而有利于后续扩展。

第3步：优化后的C语言代码

#include <iostream>

using namespace std;

const int N = 1010;
int n, cnt;
int w[N], f[N];

int main() {
    cin >> n;
    for (int i = 0 ; i < n; i++) cin >> w[i];

    // 处理第一个元素，初始化长度为1，末尾为w[0]
    f[cnt++] = w[0];

    for (int i = 1; i < n; i++) {
        if (w[i] > f[cnt-1]) {
            // 情况1：可以 extending 最长子序列
            f[cnt++] = w[i];
        } else {
            // 情况2：二分查找替换位置
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (f[mid] >= w[i]) r = mid;
                else l = mid + 1;
            }
            f[r] = w[i]; // 更新较小末尾元素
        }
    }
    cout << cnt << endl;
    return 0;
}

最长公共子序列（LCS）：双序列匹配

给定两个字符串 A 和 B，求它们的最长公共子序列长度。子序列不要求字符在原串中连续，但相对顺序必须一致。

第1步：状态定义与集合划分

定义 f[i][j] 为字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度。

考虑最后一步决策，根据 A的第 i 个字符和 B的第 j 个字符是否在子序列中出现，可分为四种情况：A[i] 不在，B[j] 不在：f[i-1][j-1]A[i] 不在，B[j] 在：f[i-1][j]A[i] 在，B[j] 不在：f[i][j-1]A[i] 在，B[j] 在：仅当 A[i] == B[j] 时成立，值为 f[i-1][j-1] + 1

实际上，前三种情况可以被合并。如果我们假设 A[i] 和 B[j] 都不参与匹配，那么结果就是 max(f[i-1][j], f[i][j-1])。如果它们相等，我们再尝试更新为 f[i-1][j-1] + 1。

第2步：状态转移方程

• 若 A[i] == B[j]：f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1)。通常 f[i-1][j-1] + 1 会是最大的，但为了严谨可取max。
• 若 A[i] != B[j]：f[i][j] = max(f[i-1][j], f[i][j-1])。

在实际编码中，可以先执行 f[i][j] = max(f[i-1][j], f[i][j-1])，如果字符相等，再与 f[i-1][j-1] + 1 比较更新。

第3步：C语言代码实现

#include <iostream>

using namespace std;

const int N = 1010;

int n , m;
char a[N] , b[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    // 注意字符串读入后下标偏移，方便从1开始计算
    cin >> a + 1 >> b + 1;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            // 先继承不考虑当前字符的情况
            f[i][j] = max(f[i - 1][j] , f[i][j - 1]);
            
            // 如果字符相同，尝试匹配
            if(a[i] == b[j]) 
                f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
        }                                                       

    cout << f[n][m] << endl;
    return 0;
}

以上就是C语言线性动态规划常见模型的详细内容，更多关于C语言动态规划算法的资料请关注本站其它相关文章！