华为机试 DP 牛客实例

华为机试 DP 牛客实例（Python，可直接提交）

华为机试DP一般是一维DP为主，很少复杂二维DP。常考：最长递增子序列、最大子数组和、背包、跳台阶。
下面给2道最常考真题风格：
① 连续子数组最大和（简单DP，高频）
② 最长递增子序列LIS（中等，华为真题多次出现）

例1：最大子数组和（牛客经典，一维DP）

题目描述

给定一个整数数组，找出连续子数组的最大和。
数组元素可正可负。
输入：一行多个整数，空格分隔
输出：最大子数组和

输入样例

-2 1 -3 4 -1 2 1 -5 4

输出样例

6

解释：[4,-1,2,1] 和为6

完整可提交代码

importsysdefmain():lines=sys.stdin.read().splitlines()arr=list(map(int,lines[0].split()))n=len(arr)ifn==0:print(0)return# dp[i]：以arr[i]结尾的连续子数组最大和dp=[0]*n dp[0]=arr[0]res=dp[0]foriinrange(1,n):# 选：接上前面子数组；不选：自己单独开始dp[i]=max(arr[i],dp[i-1]+arr[i])ifdp[i]>res:res=dp[i]print(res)if__name__=="__main__":main()

空间优化版本（机试推荐，O(1)空间，不用dp数组）

importsysdefmain():lines=sys.stdin.read().splitlines()arr=list(map(int,lines[0].split()))pre=arr[0]ans=arr[0]fornuminarr[1:]:pre=max(num,pre+num)ans=max(ans,pre)print(ans)if__name__=="__main__":main()

DP状态转移：dp[i] = max(nums[i], dp[i-1]+nums[i])
含义：要么把当前数字接在前面的子数组，要么从当前数字重新开始。

例2：最长递增子序列 LIS（华为高频中等DP题）

子序列不需要连续！！重点区分【子串（连续）】vs【子序列（不连续）】

题目描述

给定数组，求最长严格递增子序列长度。
输入：一行整数
输入样例

10 9 2 5 3 7 101 18

输出

4

解释：[2,3,7,101] 长度4

DP O(n²) 版本（容易写，适合机试，数据不大直接用）

importsysdefmain():lines=sys.stdin.read().splitlines()arr=list(map(int,lines[0].split()))n=len(arr)ifn==0:print(0)return# dp[i]：以arr[i]结尾的最长递增子序列长度dp=[1]*n max_len=1foriinrange(n):forjinrange(i):ifarr[j]<arr[i]:ifdp[j]+1>dp[i]:dp[i]=dp[j]+1max_len=max(max_len,dp[i])print(max_len)if__name__=="__main__":main()

状态：dp[i]以i结尾的LIS长度
转移：如果arr[j]<arr[i]，dp[i] = max(dp[i], dp[j]+1)

优化O(n log n)版本（数据量大，n>1000时用）

importsysimportbisectdefmain():lines=sys.stdin.read().splitlines()arr=list(map(int,lines[0].split()))tails=[]forxinarr:idx=bisect.bisect_left(tails,x)ifidx==len(tails):tails.append(x)else:tails[idx]=xprint(len(tails))if__name__=="__main__":main()

例3：跳台阶（简单DP，华为真题，斐波那契变形）

题目描述

一次可以跳1级或者2级台阶，求跳到n级总方法数
输入：n
样例输入：5
输出：8

importsysdefmain():lines=sys.stdin.read().splitlines()n=int(lines[0])ifn<=2:print(n)returndp=[0]*(n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]print(dp[n])if__name__=="__main__":main()

状态：dp[i]到达第i阶方案数
转移：dp[i] = dp[i-1] + dp[i-2]
最后一步跳1阶，或者跳2阶

DP做题四步法（机试写DP固定流程，必背）

1. 定义dp数组含义：dp[i]代表什么（最关键！定义错直接全错）
2. 找初始条件 base casedp[0], dp[1]
3. 推导状态转移方程，从小例子手动验算
4. 遍历顺序：一维一般从左向右

DP机试避坑

1. 区分子串（连续）和子序列（可不连续），题目读仔细
2. 初始化！很多人忘记初始化dp数组，出现负数、0错误
3. 空间能优化就优化，一维dp经常只需要保存前一个值
4. 数据范围大的时候，O(n²)会超时，改用二分优化LIS
5. 数组下标：从0还是从1开始，不要混用

DP选型速查

要不要再来01背包完整样题（华为偶尔考二维DP）？