华为笔试刷题1：动态规划

前言

这是华为的笔试刷题笔记1

题目包括：

2026年1月22日-100分-投资最大收益周期
2025年7月9日-300分-无线网络覆盖计划
2024年11月20日-200分-服务器休息计划
2022年10月12日-100分-D路通信
2025年10月17日-100分-奖品兑换组合
2025年5月14日-200分-游戏中的地图穿越
2025年6月11日-200分-网络整改
2025年6月11日-300分-命令行参数提示
2023年10月12日-200分-滑雪冒险
2023年05月10日-300分-快乐校园跑

题目详解

1）投资最大收益周期

常规动态规划，转移方程为dp[i] = max(dp[i - 1] + nums[i], nums[i]);

本题是取一段连续的最大子数组，因此考虑是否加入nums[i]

2）无线网络覆盖计划

本题是典型的01背包问题：倒序遍历

public class Main {
    public static int zeroOneKnapsack(int[] weight, int[] value, int bagSize) {
        int n = weight.length;
        int[] dp = new int[bagSize + 1];

        for (int i = 0; i < n; i++) {
            // 01 背包容量必须倒序遍历
            for (int j = bagSize; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        return dp[bagSize];
    }

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;

        System.out.println(zeroOneKnapsack(weight, value, bagSize)); // 35
    }
}

3）服务区休息计划

dp[i]表示在第i个服务区休息的情况下的最小花费

注意初始化dp时，前M个服务区初始化的dp值是它们本身的花费

最后取倒数M个服务区的最小花费即可

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] cost = new int[N];
        for(int i = 0; i < N; ++i){
            cost[i] = in.nextInt();
        }
        int[] dp = new int[N];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < Math.min(N, M); i++) {
            dp[i] = cost[i];
        }
        for(int i = 1; i < N; ++i){
            for(int j = i - 1; j >= i - M && j >= 0; --j){
                dp[i] = Math.min(dp[i], dp[j] + cost[i]);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = N - 1; i>= N  - M  && i >= 0 ;--i){
            min = Math.min(min, dp[i]);
        }
        System.out.println(min);
    }
}

4）D路通信

注意最长公共子串和最长公共子序列的区别：

子串一定是连续的，因此如果当前i和j的字母不同，dp(i)(j)为0

对于最长公共子序列，需要将状态转移给dp(i-1)(j)或dp(i)(j-1)

5）奖券兑换组合

01背包：最多选1次

完全背包：可以选无限次

多重背包：最多选指定次数

本题是多重背包：

dp[i][s] = dp[i - 1][s]
         + dp[i - 1][s - v]
         + dp[i - 1][s - 2v]
         + ...
         + dp[i - 1][s - cnt * v]

import java.util.*;

public class Main {
    public static void main(String[] agrs){
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < len; ++i){
            int value = in.nextInt();
            map.put(value, map.getOrDefault(value, 0) + 1);
        }
        int num = in.nextInt();
        int[] dp = new int[num + 1];
        dp[0] = 1;
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            int v = e.getKey();
            int cnt = e.getValue();
            int[] next = new int[num + 1];
            for(int i = 0; i < num + 1; ++i){
                for(int k = 0; k <= cnt && k * v <= i; ++k){
                    next[i] += dp[i - k * v];
                }
            }
            dp = next;
        }
        System.out.println(dp[num]);
    }
  
}

1. 方案数最开始初始化为1
2. 熟悉Entry的写法
3. 熟悉多重背包的写法

6）游戏中的地图穿越

二维dp，但不能使用整型最大值，可能会出现溢出的情况

7）网络整改（学习80min）

错误代码,，错误原因在于移除节点后，剩余的节点有可能会升级成叶子节点

import java.util.*;
public class Main{
    static int dis = 0;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<List<Integer>> list = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            list.add(new ArrayList<>());
        }
        for(int i = 0; i < n - 1; ++i){
            int first = in.nextInt();
            int second = in.nextInt();
            list.get(first - 1).add(second);
        }
        // ArrayList<Integer> edge = new ArrayList<>();
        // for(int i = 0; i < n; ++i){
        //     if(list.get(i).size() == 0)
        //         edge.add(i + 1);
        // }
        ArrayList<Integer> distance = new ArrayList<>();
        dfs(distance, list, 0);
        //找到distance数组中出现次数最多的频率
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < distance.size(); ++i){
            map.put(distance.get(i), map.getOrDefault(distance.get(i), 0) + 1);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for(int cnt : map.values()){
            ans.add(cnt);
        }
        ans.sort(Collections.reverseOrder());
        System.out.println(distance.size() - ans.get(0));
       
        
    }
    static void dfs(ArrayList<Integer> distance,ArrayList<List<Integer>> list , int root){
        if(list.get(root).size() == 0){
            distance.add(dis);
        }
        for(int i = 0; i < list.get(root).size(); ++i){
            dis++;
            dfs(distance, list, list.get(root).get(i) - 1);
            dis--;
        }

    }
}

正确代码如下：

import java.util.*;
public class Main{
    static List<List<Integer>> adj;
    static List<List<Integer>> children;
    static int maxDepth = 0;
    static int[] depth;
    static void dfs(int u, int p){
        for(int v : adj.get(u)){
            if(v == p)
                continue;
            depth[v] = depth[u] + 1;
            maxDepth = Math.max(depth[v], maxDepth);
            children.get(u).add(v);
            dfs(v, u);
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        adj = new ArrayList<>();
        for(int i = 0; i <= n; ++i)
            adj.add(new ArrayList<>());
        for(int i = 0; i < n - 1; ++i){
            int first = in.nextInt();
            int second = in.nextInt();
            adj.get(first).add(second);
        }   
        depth = new int[n + 1];
        children = new ArrayList<>();
        for(int i = 0; i <= n; ++i) children.add(new ArrayList<>());
        dfs(1, 0);
        int ans = 0;
        List<List<Integer>> byDepth = new ArrayList<>();
        for(int i = 0; i <= maxDepth; ++i) byDepth.add(new ArrayList<>());
        for(int v = 1; v <= n; ++v) byDepth.get(depth[v]).add(v);
        for(int h = 0; h <= maxDepth; ++h){
            int[] best = new int[n + 1];
            Arrays.fill(best, Integer.MIN_VALUE/2);
            for(int d = maxDepth; d >= 0; d--){
                for(int v: byDepth.get(d)){
                    if(d > h){
                        best[v] = Integer.MIN_VALUE/2;
                    }else if(d == h){
                        best[v] = 1;
                    }
                    else{
                        int sum = 0;
                        for(int u: children.get(v)){
                            if(best[u] > 0) sum += best[u];
                        }
                        best[v] = (sum > 0 ? sum + 1: Integer.MIN_VALUE/2);



                    }
                }
            }
            ans = Math.max(ans, best[1]);
        }
        System.out.println(n - ans);
    }
}

核心思路

1、树型dp

2、删除最少 转换成保留最多

8）命令行参数提示

import java.util.*;
public class Main{
    static class Node{
        int index;
        int distance;
        public Node(int i, int d){
            index = i;
            distance = d;
        }


    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int D = in.nextInt();
        int N = in.nextInt();
        String[] demands = new String[N];
        for(int i = 0; i < N; ++i){
            demands[i] = in.next();
        }
        String target = in.next();
        int[] distances = new int[N];
        boolean cnt = false;
        for(int i = 0; i < N; ++i){
            distances[i] = editDistance(demands[i], target);

            if(distances[i] == 0)
            {
                System.out.println(demands[i]);
                return;
            }else if(distances[i] <= D){
                cnt = true;
            }
        }
        if(!cnt){
            System.out.println("None");
        }else{
            Node[] nodes = new Node[N];
            for(int i = 0; i < N; ++i){
                nodes[i] = new Node(i, distances[i]);
            }
            Arrays.sort(nodes, (a, b) -> {
                if (a.distance != b.distance) {
                    return Integer.compare(a.distance, b.distance);
                }
                return demands[a.index].compareTo(demands[b.index]);
            });
            for(int i = 0; i < N; ++i){
                if(nodes[i].distance <= D){
                    System.out.print(demands[nodes[i].index] + " ");
                }else{
                    break;
                }
            }
        }


    }
    static int editDistance(String mm, String nn){
        int m = mm.length();
        int n = nn.length();
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i < m + 1; ++i){
            dp[i][0] = i; 
        }
        for(int j = 0; j < n + 1; ++j){
            dp[0][j] = j;
        }
        for(int i = 1; i < m + 1; ++i){
            for(int j = 1; j < n + 1; ++j){
                int left = dp[i][j - 1] + 1;
                int down = dp[i - 1][j] + 1;
                int leftDown = dp[i - 1][j - 1];
                if(mm.charAt(i - 1) != nn.charAt(j - 1))
                    leftDown += 1;
                dp[i][j] = Math.min(left, Math.min(down, leftDown) );
            }
        }
        return dp[m][n];
    }
}

1. 注意在写边界+1的dp时的遍历终点
2. 字典序用的是compareTo

9）滑雪冒险

import java.util.*;
public class Main{
    static class Node{
        int h;
        int i;
        int j;
        public Node(int h, int i, int j){
            this.h = h;
            this.i = i;
            this.j = j;
        }
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int R = in.nextInt();
        int C = in.nextInt();
        int[][] map = new int[R][C];
        Node[] nodes = new Node[R * C];
        int k = 0;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                map[i][j] = in.nextInt();
                nodes[k] = new Node(map[i][j], i, j);
                k++;
            }
        }
        Arrays.sort(nodes, (a , b) -> b.h - a.h);

        int[][] dp = new int[R][C];
        int[][] d = new int[][]{{-1, 0},{1,0},{0, -1}, {0, 1}};
        int max = 0;
        for(int i = 1; i < R*C; ++i){
            int h = nodes[i].h;
            int m = nodes[i].i;
            int n = nodes[i].j;
            for(int j = 0; j < 4; ++j){
                int ii = m + d[j][0], jj = n + d[j][1];
                if(ii >= 0 && jj >=0 && ii < R && jj < C && map[ii][jj] > h){
                    dp[m][n] = Math.max(dp[m][n], dp[ii][jj] + 1);
                }
            }
            max = Math.max(max, dp[m][n]);
        }
        System.out.println(max + 1);

    }
}

把最高点作为初始状态，然后依次遍历，是排序+动态规划

第二种方法是dfs+记忆化搜索

import java.util.*;

public class Main {
    // 定义滑雪场的高度数组和记忆化数组
    static int[][] g = new int[210][210]; // g[i][j]表示(i,j)点的高度
    static int[][] f = new int[210][210]; // f[i][j]表示从(i,j)开始的最大滑雪路径长度
    static int n, m; // n为行数，m为列数
    // 四个方向的偏移量，分别是上、下、左、右
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

    // 深度优先搜索函数
    static int dfs(int x, int y) {
        // 如果该点的最大路径长度已经计算过，直接返回
        if (f[x][y] != -1) return f[x][y];
        f[x][y] = 1; // 初始化路径长度为1（包括当前点）
        int t = 0; // 用于记录可达的最大路径长度

        // 遍历四个相邻的方向
        for (int i = 0; i < 4; i++) {
            int a = dx[i] + x, b = dy[i] + y; // 计算相邻点的坐标
            // 检查边界条件和高度条件，确保只向低于当前高度的点滑动
            if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] >= g[x][y]) continue;
            // 递归调用DFS函数计算相邻点的最大路径长度
            t = Math.max(t, dfs(a, b));
        }

        // 更新当前点的最大路径长度
        f[x][y] += t;
        return f[x][y]; // 返回当前点的最大路径长度
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建输入扫描器
        n = sc.nextInt(); // 输入行数
        m = sc.nextInt(); // 输入列数
        // 输入每个点的高度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = sc.nextInt();
            }
        }

        // 初始化记忆化数组f为-1，表示尚未计算
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], -1); // 将每一行的所有值设置为-1
        }

        int res = 1; // 记录最长路径长度，初始为1
        // 对每个点调用DFS函数计算最大路径长度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = Math.max(res, dfs(i, j)); // 更新最长路径
            }
        }

        // 输出最长滑雪路径长度
        System.out.println(res);
    }
}

10）快乐校园跑（解题75min, 学习45min, 总时长120min）

错误代码，且用时75min，试图用回溯思路解题，但过程中漏洞百出，需要加强回溯的写法，同时也要加强图论部分的学习

import java.util.*;
public class Main{
    static ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] runTimes = new int[n][n];
        for(int i = 0; i < m; ++i){
            int start = in.nextInt() - 1;
            int end = in.nextInt() - 1;
            int time = in.nextInt();
            runTimes[start][end] = time;
        }


        int from = in.nextInt();
        boolean[] visited = new boolean[n];
        for(int i = 0; i < runTimes[from-1].length; ++i){
            if(from != i + 1 && runTimes[from-1][i] != 0){
                ArrayList<Integer> path = new ArrayList<>();
                path.add(from);
                dfs(runTimes, i + 1,visited, path);
            }
            Arrays.fill(visited, false);
               
        }
         
        // 最多必经点数
        Set<Integer> set = new HashSet<>();
        int[] totolTime = new int[paths.size()];
        for(int i = 0; i < paths.size(); ++i){
            List<Integer> path = paths.get(i);
            for(int j = 0; j < path.size(); ++j){
                int k = path.get(j);
                set.add(k);
                if (j != 0)
                    totolTime[i] += runTimes[path.get(j - 1)][k] + runTimes[k][k];
            }
        }
        List<Integer> location_min_time = new ArrayList<>();
        for(int location : set){
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < paths.size(); ++i){
                 List<Integer> path = paths.get(i);
                if(path.contains(location)){
                    min = Math.min(min, totolTime[i]);
                }
            }
            location_min_time.add(min);
            
        }
        int max = Collections.max(location_min_time);
        System.out.println(set.size());
        System.out.println(max);


        }

        static void dfs(int[][] runTimes, int from, boolean[] visited, ArrayList<Integer> path){
        if(visited[from - 1]){
            paths.add(new ArrayList<>(path));
            
            return;
        }
        for(int i = 0; i < runTimes[from-1].length; ++i){
            if(from != i + 1 && runTimes[from-1][i] != 0){
              
                path.add(from);
                visited[from - 1] = true;
                dfs(runTimes, i + 1, visited, path);
            }
               
        }
        
    }
    }
  

正确思路：floyd最短路径

算法模板：

//算法主体
     for(int k = 1; k <= n; ++k){
         for(int i = 1; i <= n; ++i){
             if(f[i][k] == INF)
                 continue;
             for(int j = 1; j <= n; ++j){
                 if(f[k][j] == INF)
                     continue;
                 if(f[i][k] + f[k][j] < f[i][j])
                     f[i][j] = f[i][k] + f[k][j];
             } 
         }
     }

本题核心

1、建模成floyd算法问题（尤其是图中点的数量在100左右）

最多必经点数建模成floyd中的起点的可达点数

最终成绩时间建模成floyd中的起点到各个可达点的最小值

2、考虑小游戏时间添加到a->b的路径长度当中