华为OD机试题中 动态规划和贪心算法例题_华为od 梦想橡皮擦

在 ACM 比赛中，有许多常见的编程算法和数据结构经常被使用。本系列博客会罗列各种常见算法，以及其代表性例题。

这部分内容可以用于类似华为 OD 机考学习。

动态规划

动态规划是一种将复杂问题分解为简单子问题并使用子问题的解来构建更大问题的方法。它通常用于解决最长公共子序列、背包问题、最优化问题等。

题目：最长递增子序列

描述

给定一个整数序列，找出其中最长的递增子序列的长度。递增子序列是指序列中的元素按照非降序排列，并且元素之间可以不连续。

输入

输入的第一行包含一个整数 n（$1\le n\le 10^3$），表示序列的长度。
接下来一行包含 n 个整数，表示序列中的元素。

输出

输出一个整数，表示最长的递增子序列的长度。

注意

子序列不要求连续，只要求元素按照非降序排列即可。
序列中的元素可能存在重复。

示例

输入

8
2 4 3 5 1 7 6 9
1
2

输出

5
1

解释
在给定序列中，最长的递增子序列是 2 3 5 7[6] 9，长度为 5。

AC 题解代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以第i个元素结尾的最长递增子序列的长度

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int result = longestIncreasingSubsequence(nums);
    cout << result << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

贪心算法

贪心算法是一种每次选择当前最优解的策略。它通常用于优化问题，例如最短路径、最小生成树等。

题目：零钱兑换

描述

给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币数量。如果无法凑成总金额，则返回-1。

假设每种硬币的数量是无限的。

输入

输入由两行组成。
第一行包含一个整数 n（$1\le n\le 10^3$），表示硬币的种类数。
第二行包含 n 个整数，表示每种硬币的面额（$1\le coins[i]\le 10^4$）。

接下来一行包含一个整数 amount（$1\le amount\le 10^5$），表示要凑成的总金额。

输出

输出一个整数，表示凑成总金额所需的最少硬币数量。如果无法凑成总金额，则输出-1。

注意

如果没有硬币面额可以组成总金额，返回-1。
如果存在多种组合方式，返回最少硬币数量的方案。

示例

输入

4
1 2 5 10
15
1
2
3

输出

2
1

解释
使用面额为 10、5 的硬币，可以凑成总金额 15，所需的最少硬币数量为 2。

AC 题解代码

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.size(); j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }

    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int n;
    cin >> n;

    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    int amount;
    cin >> amount;

    int result = coinChange(coins, amount);
    cout << result << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

欢迎继续学习