CSP-J 卷

使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。

下面的 fiboA() 和 fiboB() 两个函数分别实现斐波那契数列，该数列第 $1$、第 $2$ 项值为 $1$，其余各项分别为前两项之和。下面有关说法错误的是（ ）。

01int fiboA(int n)
02{
03    if(n==0)
04        return 1;
05    if(n==1)
06        return 1;
07    else
08    {
09        return fiboA(n-1)+fiboA(n-2);
10    }
11}
12int fiboB(int n)
13{
14    if( (n==0) || (n==1) ){
15        fiboB[n]=n;
16        return n;
17    }
18    else{
19        if(fiboB[n] == 0){
20            fiboB[n]=FiboB(n-1)+FiboB(n-2);
21        }
22        return fiboB[n];
23    }
24}

在求解最优化问题时，动态规划常常涉及到两个重要性质，即最优子结构和（ ）。

在动态规划中，状态转移方程的作用是定义状态之间的关系。

应用动态规划算法时，识别并存储重叠子问题的解是必须的。

关于动态规划的描述，正确的是（）。

以下关于动态规划算法特性的描述，正确的是（）。

动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题。

状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。

动态规划通常用于解决（ ）。

下面递归实现的斐波那契数列的时间复杂度为 $O(2^n)$。

01long long fib_memo(int n, long long memo[]) {
02    if (n <= 1) return n;
03    if (memo[n] != -1) return memo[n];
04    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
05    return memo[n];
06}
07
08int main() {
09    int n = 40;
10    long long memo[100];
11    fill_n(memo, 100, -1);
12    long long result2 = fib_memo(n, memo);
13    return 0;
14}

下面程序的输出为（ ）。

01#include <iostream>
02using namespace std;
03int rec_fib[100];
04int fib(int n) {
05    if (n <= 1)
06        return n;
07    if (rec_fib[n] == 0)
08        rec_fib[n] = fib(n - 1) + fib(n - 2);
09    return rec_fib[n];
10}
11int main() {
12    cout << fib(6) << endl;
13    return 0;
14}

在动态规划问题中，状态空间相同且没有重复计算的情况下，“状态转移方程+递推”与“递归+记忆化搜索”的时间复杂度通常相同。

青蛙每次能跳 $1$ 或 $2$ 步。下面是青蛙跳到第 $N$ 步台阶 C++ 实现代码。该段代码采用的算法是（ ）。

01int jumpFrog(int N) {
02    if (N <= 3)
03        return N;
04    return jumpFrog(N - 1) + jumpFrog(N - 2);
05}

元宵节晚上，小朋友沿着一条发光石板路前进，每次可向前走 $1$ 块或 $2$ 块石板。动态规划定义如下：dp[i] = dp[i - 1] + dp[i - 2]，下面关于 dp[i] 的含义最合适的是（）。

以下动态规划算法的含义与目的是（ ）。

01int function(vector<int>& nums) {
02    int n = nums.size();
03    if (n == 0)
04        return 0;
05    if (n == 1)
06        return nums[0];
07    vector<int> dp(n, 0);
08    dp[0] = nums[0];
09    dp[1] = max(nums[0], nums[1]);
10    for (int i = 2; i < n; ++i) {
11        dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
12    }
13    return dp[n - 1];
14}

小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下代码实现，请补全横线。

01int visit(vector<int>& nums) {
02    if (nums.empty()) {
03        return 0;
04    }
05    int size = nums.size();
06    if (size == 1)
07        return nums[0];
08
09    vector<int> dp = vector<int>(size, 0);
10    dp[0] = nums[0];
11    dp[1] = max(nums[0], nums[1]);
12
13    for (int i = 2; i < size; i++) {
14        dp[i] = ____________; // 在此处填写代码
15    }
16
17    return dp[size - 1];
18}

在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4]，目标金额为 $6$，则最少需要 $2$ 枚硬币（3+3）。

小杨在玩一个闯关游戏，从第 $1$ 关走到第 $4$ 关。每一关的体力消耗如下（下标表示关卡编号）：cost = [0, 3, 5, 2, 4]，其中 cost[i] 表示到达第 $i$ 关需要消耗的体力，cost[0]=0 表示在开始状态，体力消耗为 $0$。小杨每次可以从当前关卡前进 $1$ 步或 $2$ 步。按照上述规则，从第 $1$ 关到第 $4$ 所需消耗的最小体力为 $7$。

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。下面横线处应该填入的是（ ）

01#include <iostream>
02#include <vector>
03#include <algorithm>
04using namespace std;
05int maxSubArray(vector<int>& nums) {
06    int n = nums.size();
07    if (n == 0) return 0;
08    vector<int> dp(n, 0);
09    dp[0] = nums[0];
10    int maxSum = dp[0];
11    for (int i = 1; i < n; i++) {
12        ____________
13        maxSum = max(maxSum, dp[i]);
14    }
15    return maxSum;
16}
17int main() {
18    int n;
19    cin >> n;
20    vector<int> nums(n);
21    for (int i = 0; i < n; i++) {
22        cin >> nums[i];
23    }
24    int result = maxSubArray(nums);
25    cout << result << endl;
26    return 0;
27}

给定一个 $m \times n$ 的二维网格 grid，每个格子中有一个非负整数。请找出一条从左上角 $(0,0)$ 到右下角 $(m-1,n-1)$ 的路径，使得路径上的数字总和最小。每次只能向右或向下移动。横线处应该填入的是（ ）

01#include <iostream>
02#include <vector>
03#include <algorithm>
04using namespace std;
05int minPathSum(vector<vector<int>>& grid) {
06    int m = grid.size();
07    int n = grid[0].size();
08    vector<vector<int>> dp(m, vector<int>(n, 0));
09    dp[0][0] = grid[0][0];
10    for (int j = 1; j < n; j++) {
11        dp[0][j] = dp[0][j - 1] + grid[0][j];
12    }
13    for (int i = 1; i < m; i++) {
14        dp[i][0] = dp[i - 1][0] + grid[i][0];
15    }
16    for (int i = 1; i < m; i++) {
17        for (int j = 1; j < n; j++) {
18            ____________
19        }
20    }
21    return dp[m - 1][n - 1];
22}
23int main() {
24    int m, n;
25    cin >> m >> n;
26    vector<vector<int>> grid(m, vector<int>(n));
27    for (int i = 0; i < m; i++) {
28        for (int j = 0; j < n; j++) {
29            cin >> grid[i][j];
30        }
31    }
32    int result = minPathSum(grid);
33    cout << result << endl;
34    return 0;
35}

给定一个整数数组 nums，找到其中最长的严格上升子序列的长度。子序列是指从原数组中删除一些元素（或不删除）后，剩余元素保持原有顺序的序列。下面的程序横线处应该填入的是（ ）

01#include <iostream>
02#include <vector>
03#include <algorithm>
04using namespace std;
05int lengthOfLIS(vector<int>& nums) {
06    int n = nums.size();
07    if (n == 0) return 0;
08    vector<int> dp(n, 1);
09    for (int i = 1; i < n; i++) {
10        for (int j = 0; j < i; j++) {
11            if (nums[i] > nums[j]) {
12                ____________
13            }
14        }
15    }
16    return *max_element(dp.begin(), dp.end());
17}
18int main() {
19    int n;
20    cin >> n;
21    vector<int> nums(n);
22    for (int i = 0; i < n; i++) {
23        cin >> nums[i];
24    }
25    int result = lengthOfLIS(nums);
26    cout << result << endl;
27    return 0;
28}

已知三个序列：s1={3，1，8，2，5，6，7，4}，s2={1，5，1，8，6，4，7，5，6}，s3={1，8，3，5，7，6，2，4}。以下哪个序列是它们的最长公共子序列()。

假设背包的最大容量 $W = 8\text{kg}$，共有 $4$ 个物品可供选择，$4$ 个物品重量分别为 weights = [2, 3, 5, 7]，价值 values = [30, 40, 60, 80]，则该0/1背包问题中最大价值为（）。

在解决简单背包问题时，动态规划的状态转移方程如下：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);

该方程表示：在考虑第 $i$ 个物品时，当前背包容量为 $w$，如果不放物品 $i$，则最大价值是 dp[i-1][w]；如果放入物品 $i$，则最大价值是 dp[i-1][w - weights[i-1]] + values[i-1]，其中数组 weights 和 values 分别表示所有物品的重量和值，数组下标从 $0$ 开始。

给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 wt[i] 和价值 val[i]，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$，则横线上应填写（）。

01int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
02    vector<int> dp(W+1, 0);
03    for (int i = 0; i < n; ++i) {
04        for (int w = W; w >= wt[i]; --w) {
05            ____________ // 在此处填写代码
06        }
07    }
08    return dp[W];
09}

下列代码实现了一个 0-1 背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历（即 for (int j = w[i]; j <= W; j++)），仍能得到正确答案。

01int main() {
02    int W = 5;
03    int w[] = {2, 3, 4};
04    int v[] = {10, 1, 1};
05    int n = 3;
06    int dp[6] = {0};
07
08    for (int i = 0; i < n; i++) {
09        for (int j = W; j >= w[i]; j--) {
10            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
11        }
12    }
13    cout << dp[W];
14}

下面代码是一维数组优化 $0/1$ 背包的核心片段，其中 $w[i]$ 表示第 $i$ 件物品的重量，$v[i]$ 表示第 $i$ 件物品的价值。横线处应填入（ ）。

01for (int i = 1; i <= n; i++) {
02    for (int c = W; c >= w[i]; c--) {
03        __________;
04    }
05}

下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是：5 1 7 3 5 9，则输出是（ ）。

01int a[2023], f[2023];
02int main()
03{
04    int n,i,j,ans = -1;
05
06    cin>>n;
07    for( i=1; i<=n; i++){
08        cin >> a[i];
09        f[i] = 1;
10    }
11
12    for( i=1; i<=n; i++)
13        for( j=1; j<i; j++)
14            if(a[j] < a[i])
15                f[i] = max(f[i], f[j]+1);
16    for( i=1; i<=n; i++){
17        ans = max(ans, f[i]);
18        cout << f[i] << "  ";
19    }
20
21    cout << ans << endl;
22    return 0;
23}

已知两个序列 s1={1,3,4,5,6,7,7,8,1}、s2={3,5,7,4,8,2,9,5,1}，则它们的最长公共子序列是（ ）。

动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。（ ）

下⾯最长公共⼦序列程序中，横线处应该填⼊的是（ ）。

01#define MAX(A, B) (((A) > (B)) ? (A) : (B))
02#define MIN(A, B) (((A) < (B)) ? (A) : (B))
03int dp[MAX_L + 1][MAX_L + 1];
04int LCS(char str1[], char str2[]) {
05    int len1 = strlen(str1);
06    int len2 = strlen(str2);
07    for (int i = 0; i < len1; i++)
08        for(int j = 0; j < len2; j++)
09            if (str1[i] == str2[j])
10                dp[i + 1][j + 1] = dp[i][j] + 1;
11            else
12                ___________;    // 在此处填入选项
13    return dp[len1][len2];
14}

下面LIS函数试图求出最长上升子序列的长度，横线处应该填入的是( )

01int max(int a, int b) { 
02    return (a > b) ? a : b;
03}
04int LIS(vector<int> & nums) {
05    int n = nums.size(); 
06    if (n == 0) return 0;
07    vector<int> dp(n, 1);
08    int maxLen = 1;
09    for (int i = 1; i < n; i++) { 
10        for (int j = 0; j < i; j++)
11            if (nums[j] < nums[i])
12                ; // 在此处填入选项
13        maxLen = max(maxLen, dp[i]);
14    }
15    return maxLen;
16}