2025 年 春季 算法设计与分析（人工智能）oj答案

week 2 水平测（难度高）

week 3 ：递归和分治

1. 魔法符文
   题目：选出超出一半的字符
   思路：摩尔投票法
2. 英雄排名
   题目：找逆序对
   思路： merge sort找逆序对
3. 星海信息序列
   题目：在长度无限的递归构造字符串中，高效统计前 pos 位里 'S' 的个数
   思路：分治 + 对称 + 状态记忆
4. 梦幻料理学院
   题目：计算所有满足相邻餐盘菜品不同、首尾也不同的排列方式数量（总共三道菜）
   思路：状态压缩 + 动态规划
5. 最受欢迎的颜色
   题目：找出出现一半次数的数字
   思路：排序，输出中间值

week 4 ：分治和递归

1. 找重复
   题目：找出重复选择的英雄编号
   思路：哈希表
2. 连招顺序
   题目：表达式的括号插入全组合问题
   思路：分治 + 递归搜索
3. 最大数值和
   题目：最大连续子数组
   思路：kadane算法
4. 跳一跳
   题目：可以跳1、2、3步，求长度n下的跳跃方案
   思路：动规，jump(n) = jump(n-1) + jump(n-2) + jump(n-3)
5. 平分战力
   题目：将数组分为两个子数组，使得两数组和相等（0-1背包问题）
   思路：动态规划，dp[i]为是否可以组成和为i的子数组
   dp[j] = dp[j] || dp[j - num];

week 5 ：动态规划

1. 最大数值和
   题目：三角形，只能向下或右下，求路径最大
   思路：动态规划，dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
2. 战斗力总和
   题目：0-1背包问题
3. 完全战斗力总和
   题目：完全背包问题
4. 最长递增队伍
   题目：最长严格递增连续子数组的长度
   思路：动态规划，if(num[i]<num[j]) dp[i] = max(dp[i], dp[j] + 1);
5. 编辑阵容
   题目：对于每个查询字符串 t 和一个允许的最大编辑距离 num，统计有多少个字符串与 t 的编辑距离小于 num
   思路：动规，计算字符串与目标串的距离是否小于目标次数
   if (s[i - 1] == t[j - 1]) {
   dp[i][j] = dp[i - 1][j - 1];
   }
   else {
   dp[i][j] = 1 + min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] });
   }

week 8

1. 装备资源
2. 能量需求
3. 找零
4. 传送费用
5. 移除数字

week 9

1. 法力水量
2. 传送能量

week 12：分支界限算法

1. 英雄选拔
   题目：0-1背包问题
2. 五军对决
   题目：寻找总分最高的分配方式（指派问题）
   思路： 【剪枝1】当前得分 + 剩余最大潜力值（上界估计）小于当前已知最优值，则剪掉
   【剪枝2】若当前位置已被访问（已分配），跳过
3. 峡谷夺宝
   题目：最短哈密顿回路
   思路： 状态压缩动态规划

期末上机

1. 最大数值和
   题目：求最大连续子数组
   思路：暴搜可以过，但理论上应该用递归分治（week4 T3）
2. 最大利润
   和week6第四题一模一样
3. 完美战令
   题目：最多删除一个能否成为回文子串
4. 旅游计划
   题目：哈密顿最小路径