算法设计与分析学习笔记

动态规划大题

0、考察重点
题2，第三章的动态规划

关键词
1、找到状态（小明爬楼梯例子），状态表达的变量/属性
2、状态转移方程（核心，初始状态、结束状态、过程中一般的状态）
3、边界情况
4、函数的编写（根据状态转移方程翻译为代码，用c++或者伪代码，将状态转移方程表达出来）

1、使用动态规划策略求解最长公共子序列问题
在这个问题中，我们的目标是利用动态规划策略来找出两个序列之间的最长公共子序列（LCS）。
序列A：ABCBDAB
序列B：BDCABC

该问题需要你完成以下几个步骤：
1.状态定义：
•根据上述问题，定义动态规划中的“状态”。请描述这个状态所表达的变量或属性是什么。
2.状态转移方程：
•基于你在第一个问题中定义的状态，描述状态转移方程。请包括初始状态、结束状态以及过程中的一般状态转移。
3.边界情况：
•确定并描述这个问题的边界情况。
4.函数实现：
•使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，编写一个函数。
请确保你的代码能够清楚地体现出状态转移方程。

解答：
1.状态定义
在动态规划中，我们定义状态dp［i]［j］、为序列A的前i个元素和序列B的前j
个元素之间的最长公共子序列的长度。这里dp是一个二维数组，其中i和j分
別指代序列A和B的索引。

2.状态转移方程
状态转移方程可以描述为：
•当A[i]== B[j]时，dp[i][j］= dp[i-1][j-1］+ 1。
这意味着如果当前字符匹配，则最长公共子序列长度增加1。
•当A[i]!= B[j]时，dp[i][j]=max（dp［i-1][j], dp[i][j-1］）。
这表明，如果当前字符不匹配，
我们从左边或上边的状态中选择一个更长的序列。

初始状态：dp[O][j]、和dp[i][0]应该初始化为O，因为一个空序列与任何序列的最长公共子序列长度都为0。

3.边界情况
当i=0或j=0时，表示其中一个序列为空，此时最长公共子序列长度为0。

4.函数实现

#include <stdio.h>
#include <string.h>

// 动态规划求解最长公共子序列问题
int lcs(char *A, char *B) {
    int m = strlen(A);
    int n = strlen(B);
    int dp[m+1][n+1];
    int i, j;

    // 初始化边界条件
    for (i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    // 填充 dp 表
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (A[i-1] == B[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
            }
        }
    }

    return dp[m][n];
}

int main() {
    char A[] = "ABCBDAB";
    char B[] = "BDCABC";

    printf("Length of LCS is %d\n", lcs(A, B));
    return 0;
}

2、爬楼梯
小明面临着一个爬楼梯的挑战。楼梯共有n 级台阶。每次，小明可以选择爬上1级或2级台阶。
请使用动态规划的方法计算小明有多少种不同的方法来爬完这n级台阶。

1.找到状态：定义状态，以及它们代表的含义。
2.状态转移方程：描述状态之间的转换关系。
3.边界情况：确定算法的边界条件。
4.函数的编写：根据状态转移方程，使用C++或伪代码编写函数。

解答：
1、定义状态
在动态规划中，我们首先需要定义状态。在这个问题中，
我们可以定义状态dp［i］为到达第i级台阶的不同方法的数量。

2、状态转移方程
接下来，我们需要找到状态之间的转换关系，即状态转移方程。
由于小明可以选择爬1级或2级台阶，我们可以得出以下关系：
•要到达第i级台阶，小明可以从第i-1级台阶爬上一级。
•或者，他可以从第i-2级台阶爬上两级。
因此，状态转移方程为：
dp[i] = dp[i - 1] + dp[i - 2]

3、边界情况
确定算法的边界条件是非常重要的。对于这个问题：
•当n = 1时，只有一种方法爬到第一级台阶（即爬一级）。
•当n = 2时，有两种方法：爬两次一级台阶或直接爬两级台阶。
所以，边界条件为：
dp[1] = 1
dp[2] = 2
4、函数编写

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    int dp[11]; // 因为台阶数量不超过10，我们可以直接定义一个大小为11的数组
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    printf("Enter the number of stairs (up to 10): ");
    scanf("%d", &n);

    if (n > 0 && n <= 10) {
        printf("Number of ways to climb %d stairs: %d\n", n, climbStairs(n));
    } else {
        printf("Invalid number of stairs. Please enter a number from 1 to 10.\n");
    }
    
    return 0;
}

3、0/1背包问题
在一个0/1背包问题中，给定四件物品，每件物品都有其特定的重量和收益。
你的目标是确定哪些物品应该被放入背包中，以便在不超过背包最大载重
的情况下，使得背包中物品的总收益最大化。
物品的重量和收益分别是：
• 重量: w = [10,15,6,9]
• 收益：v =［2,5,8,1］
• 背包的最大载重：M = 32

请解决以下小问题：
1.状态定义：根据上述问题，定义动态规划中的“状态”。请描述这个状态表达的变量或属性是什么。
2.状态转移方程：基于你在第一个问题中定义的状态，描述状态转移方程。
请包括初始状态、结束状态以及过程中的一般状态转移。
3.边界情况：确定并描述这个问题的边界情况。
4.函数实现：使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，
编写一个函数。请确保你的代码能够清楚地体现出状态转移方程。

解答：
1.状态定义
状态定义
在0/1背包问题中，状态通常是用一个二维数组来定义的，记为dp[i][j]。这里：
•i表示考虑到第i件物品（1到n）。
•j表示当前背包的重量（从O到最大载重M）。
状态dp[i][j]、表示的是在考虑前i件物品，并且当前背包重量为j时，能够获得的最大收益。

2.状态转移方程
状态转移方程
状态转移方程是基于是否选择当前的物品。对于每件物品i、和每个重量j，我们有两种选择：
•不选择当前物品（即物品1不放入背包）：此时总收益保持不变，即dp[i][j] = dp[i-1][j]。
•选择当前物品（前提是背包能够承载这个物品）：此时总收益为当前物品的收益加上
剩余重量的最大收益，即dp[i][j] = dp[i-1][j-w[i]]+v[i]，其中w[i]和
v[i]分别是物品i的重量和收益。
因此，状态转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) if j>=w[i]
dp[i][j] = dp[i-1][j] if j < w[i]

3.边界情况是动态规划的初始化部分：
当i=0或j=0时，dp[i][j]=0。这意味着没有物品或没有背包容量时，收益为0。

4.函数实现

#include <stdio.h>

// 函数来计算最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 0/1背包问题的实现
int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int dp[n + 1][W + 1];

    // 构建表格dp[][]
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;//边界条件
            } else if (wt[i - 1] <= w) { //装得下，装或者不装，两者取最大值
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else { //装不下
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int val[] = {2, 5, 8, 1}; // 物品的收益
    int wt[] = {10, 15, 6, 9}; // 物品的重量
    int W = 32; // 背包的最大载重
    int n = sizeof(val) / sizeof(val[0]); // 物品的数量
    printf("最大收益是 %d\n", knapsack(W, wt, val, n));
    return 0;
}

4、投资分配问题
您作为财务分析师，有一个任务是将固定资金分配给若干个不同的投资项目，
每个项目根据不同的资金投入会有不同的收益。您的目标是在资金限制下最大化总收益。
题目的具体参数：
总资金：5万元
投资项目数：4个
每个项目有不同的收益函数 fi(x)，根据投资金额x的不同有不同的收益。
投资金额 x 必须是非负整数，且总投资额 x1 + x2 + ... + xn = m ，在本问题中 m = 5。

收益表：

任务：
请完成以下任务：
1. 状态定义：
根据上述问题，定义动态规划中的“状态”。描述这个状态所表达的变量或属性是什么。
2. 状态转移方程：
基于你在第一个问题中定义的状态，描述状态转移方程。请包括初始状态、结束状态以及过程中的一般状态转移。
3. 边界情况：
确定并描述这个问题的边界情况。
4. 函数实现：
使用C++或伪代码，根据你在第二个问题中描述的状态转移方程，编写一个函数。
请确保你的代码能夜清楚地体现出状态转移方程

解答：
1. 状态定义
在这个问题中，状态可以定义为一个二维数组dp[i][j]，其中i表示考虑到的项目数量（从1到4），
而j表示当前的总投资额（从0到5万元）。dp[i][j]的值代表在考虑前i个项目，
并且使用了j万元时能够获得的最大收益。

2.状态转移方程
状态转移方程描述了如何从一个状态转移到另一个状态。对于本问题，状态转移方程可以定义如下：
dp[i][j]= max（dp[i-1][j]，dp[i-1][j-k]+ fi（k））

其中i是项目索引，j是当前总资金，k是分配给项目i的资金， fi（k）是投资k万元在项目i上的收益。
这个方程意味着对于每个项目，我们可以选择不投资（即保持dp[i-1][j]），
或者投资某个金额（dp[i-1][j-k]+fi（k））。

初始状态：dp[0][j] = 0 对所有j，表示没有项目可以投资时的收益为0。

结束状态：dp[4][5] 表示考虑所有项目并使用了全部资金时的最大收益。

3.边界情況
边界情况包括：
•当j= 0时，即没有资金可用，所有dp[i][0] = 0。
•当i= 0时，即没有项目可选，所有dp[O][j] = 0。

4.函数实现

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int f[4][6] = {
        {0, 11, 12, 13, 14, 15},
        {0,  0,  5, 10, 15, 20},
        {0,  2, 10, 30, 32, 40},
        {0, 20, 21, 22, 23, 24}
    };

    int dp[5][6] = {0}; // 初始化dp数组

    // 第一个循环（1）：遍历所有的项目。
    // 第二个循环（j）：遍历所有的投资额。
    // 第三个循环（k）：这个循环是关键，它遍历每个项目可能的投资金额。
    for (int i = 1; i <= 4; i++) {
        for (int j = 0; j <= 5; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + f[i - 1][k]);
            }
        }
    }

    printf("最大收益: %d\n", dp[4][5]);
    return 0;
}

5、

解答：

2.时间复杂度、空间复杂度
时间复杂度：我们需要计算L[i][j]对于每个i从1到n和每个j从1到y，所以时间复杂度为O（ny）。
空间复杂度：由于我们需要存储一个大小为n*y的二维数组，因此空间复杂度也是(ny)。

3.求解：
表格的行代表了不同的硬币种类（vi 的值），列代表了我们要兑换的金额从O到y。
每个单元格L[i,j]的值表示使用前i种硬币兑换金额j所需的最少硬币数量。

第一行（v1）：仅使用面值为1的硬币时，兑换金额j所需的硬币数量直接等于金额本身（因为每枚硬币价值1）。

第二行（v2）：现在我们引入面值为5的硬币。对于金额小于5的j，我们仍然只能使用面值为1的硬币，因此值不变。
但对于j大于或等于5，我们可以开始使用面值为5的硬币。在这些情况下，L[2,j]的值可能会变小，
因为使用面值为5的硬币可能会比仅使用面值为1的硬币需要更少的硬币数量。

第三行（v3）：引入面值为7的硬币。同样的逻辑，对于金额j大于或等于7，我们考虑使用面值为7的硬币
是否可以减少所需的硬币总数。如果可以，我们更新l[3,j]的值。

第四行（v4）：最后，我们考虑面值为11的硬币。同之前的步骤，我们检查对于金额j
大于或等于11的情况，是否使用面值为11的硬币可以减少硬币数量。

每一次，我们都是在查找最小值：是否使用新的硬币种类会比不使用它需要更少的硬币数量。如果是的话，
我们就更新那个金额的最少硬币数。

L[4][15]的值为3，表示使用前四种硬币兑换金额为15需要的最少硬币数为3。
最优解：
3枚5元硬币
2枚7元硬币+1枚1元硬币
最优值：3