简单的动态规划

1、设计一个数据结构，记录不同规模的问题的答案。

2、数据结构采用从小到大的方式去生成。

上台阶：

递归：

#include <stdio.h>

int f(int n){
    if (n == 1)
    {
        return 1;
    }
    else if (n == 2)
    {
        return 2;
    }
    else{
        return f(n-1) + f(n-2);
    }
}
int main() {

    int n;
    scanf("%d",&n);
    printf("%d\n",f(n));
}

动态规划：

#include <stdio.h>

int main() {
    int dp[16] = {0};
    dp[1] = 1;
    dp[2] = 2;
    int n;
    scanf("%d",&n);
    for (int i = 3; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    printf("%d\n",dp[n]);
    return 0;
}

放苹果：

把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法?
盘子相对顺序不同，例如 5，1，1和 1，5，1算作同一种分法。

输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 M 和 N
输出格式
每组数据，输出一行一个结果表示分法数量，

输入7 3

输出 8

#include <stdio.h>

int main() {
    int dp[13][13] = { 0 };

    int m,n;
    while (scanf("%d %d",&m,&n) != EOF){
        for (int i = 0; i <= m; i++){
            dp[i][1] = 1;
        }
        for (int i = 0; i <= n; i++){
            dp[1][i] = 1;
            dp[0][i] = 1;
        }
        for (int i = 2; i <= m; i++){
            for (int j = 2; j <= n; j++){
                if (i >= j){
                    dp[i][j] = dp[i][j - 1] + dp[i -j][j];
                    //dp[i][j-1] 有空盘子  分为盘子空 1个 2个 3个 。。。 直到  dp(m)(1)
                    //dp[i-j][j] 没空盘子 把i-j个苹果放到 n个盘子里
                }else{
                    //苹果比盘子少的时候，相当于m苹果放在m盘子，空的可以不要
                    dp[i][j] = dp[i][i];
                }
        }
    }
    printf("%d\n",dp[m][n]);
    }
   return 0;
}

//苹果比盘子少的时候，相当于m苹果放在m盘子，空的可以不要

最长公共子序列：

我们有两个字符串 s1 和 s2，我们的目标是找出它们的 最长公共子序列（LCS）。LCS 是两个字符串中都出现的子序列（顺序一致，但不要求连续），且其长度最大。 

n = 6
m = 6
s1 = "abcdef"
s2 = "acdfgh"

最长公共子序列的长度是：4

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;

// 定义一个二维数组 dp，dp[i][j] 代表 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列的长度
int dp[1002][1002];

int main() {
    int n, m;
    char s1[1001];
    char s2[1001];
    
    // 输入 n 和 m（分别为字符串 s1 和 s2 的长度）
    scanf("%d %d", &n, &m);
    // 输入两个字符串 s1 和 s2
    scanf("%s %s", s1, s2);

    // 初始化 dp 数组的第一行和第一列
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;  // 第一行是空字符串与任何字符串的公共子序列长度为0
    }

    for (int j = 0; j <= n; j++) {
        dp[j][0] = 0;  // 第一列是任何字符串与空字符串的公共子序列长度为0
    }

    // 进行动态规划填表
    for (int i = 1; i <= n; i++) {  // s1 从 1 到 n（因为 i 和 j 从 1 开始）
        for (int j = 1; j <= m; j++) {  // s2 从 1 到 m
            // 如果当前字符相同（s1[i-1] 和 s2[j-1]），则 dp[i][j] = dp[i-1][j-1] + 1
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            // 否则，dp[i][j] 为 dp[i-1][j] 和 dp[i][j-1] 的较大值
            else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    // 输出最后的结果，即最长公共子序列的长度
    printf("%d\n", dp[n][m]);
    return 0;
}

2. 为什么用 max(dp[i][j-1], dp[i-1][j])？

动态规划的思想就是通过 状态转移 来从小问题的解构建大问题的解。当我们在计算 dp[i][j] 时，表示的是 s1 的前 i 个字符 和 s2 的前 j 个字符 的最长公共子序列长度。如果 s1[i-1] != s2[j-1]，那么 dp[i][j] 的值不可能通过直接将 s1[i-1] 或 s2[j-1] 加入公共子序列来得到。

• dp[i][j-1] 代表的状态是 在不考虑 s2[j-1] 的情况下，s1 的前 i 个字符和 s2 的前 j-1 个字符的 LCS 长度。
• dp[i-1][j] 代表的状态是 在不考虑 s1[i-1] 的情况下，s1 的前 i-1 个字符和 s2 的前 j 个字符的 LCS 长度。

因此，当字符不相等时，我们不能直接将当前字符加入 LCS，而是需要选择跳过一个字符，来得到最长的公共子序列。max(dp[i][j-1], dp[i-1][j]) 的作用就是选择这两种跳过的方式中的 较长的公共子序列长度。

3. 举个例子解释：

假设有两个字符串：

• s1 = "abc"
• s2 = "ac"

我们希望计算它们的 LCS。我们从 dp[3][2] 计算起，表示 s1 的前 3 个字符和 s2 的前 2 个字符的最长公共子序列长度。

• 在 dp[3][2] 处，s1[2] 是 c，s2[1] 也是 c，它们相同，所以 dp[3][2] = dp[2][1] + 1。此时，LCS 长度是 2。

如果我们考虑 s1[2] 和 s2[1] 不相等的情况（假设 s1[2] != s2[1]），比如有一个字符串是 "abc"，另一个是 "def"，那么在 dp[3][3] 处，我们就需要通过跳过 s1[2] 或 s2[2] 中的一个来计算 LCS：

• dp[3][2] 表示 跳过 s2[2]，即只考虑 s1[0..2] 和 s2[0..1]。
• dp[2][3] 表示 跳过 s1[3]，即只考虑 s1[0..1] 和 s2[0..2]。

最终，我们用 max(dp[2][3], dp[3][2]) 选出更长的公共子序列长度。