华为机试 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():linessys.stdin.read().splitlines()arrlist(map(int,lines[0].split()))nlen(arr)ifn0:print(0)return# dp[i]以arr[i]结尾的连续子数组最大和dp[0]*n dp[0]arr[0]resdp[0]foriinrange(1,n):# 选接上前面子数组不选自己单独开始dp[i]max(arr[i],dp[i-1]arr[i])ifdp[i]res:resdp[i]print(res)if__name____main__:main()空间优化版本机试推荐O(1)空间不用dp数组importsysdefmain():linessys.stdin.read().splitlines()arrlist(map(int,lines[0].split()))prearr[0]ansarr[0]fornuminarr[1:]:premax(num,prenum)ansmax(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] 长度4DP O(n²) 版本容易写适合机试数据不大直接用importsysdefmain():linessys.stdin.read().splitlines()arrlist(map(int,lines[0].split()))nlen(arr)ifn0:print(0)return# dp[i]以arr[i]结尾的最长递增子序列长度dp[1]*n max_len1foriinrange(n):forjinrange(i):ifarr[j]arr[i]:ifdp[j]1dp[i]:dp[i]dp[j]1max_lenmax(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)版本数据量大n1000时用importsysimportbisectdefmain():linessys.stdin.read().splitlines()arrlist(map(int,lines[0].split()))tails[]forxinarr:idxbisect.bisect_left(tails,x)ifidxlen(tails):tails.append(x)else:tails[idx]xprint(len(tails))if__name____main__:main()例3跳台阶简单DP华为真题斐波那契变形题目描述一次可以跳1级或者2级台阶求跳到n级总方法数输入n样例输入5输出8importsysdefmain():linessys.stdin.read().splitlines()nint(lines[0])ifn2:print(n)returndp[0]*(n1)dp[1]1dp[2]2foriinrange(3,n1):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固定流程必背定义dp数组含义dp[i]代表什么最关键定义错直接全错找初始条件 base casedp[0], dp[1]推导状态转移方程从小例子手动验算遍历顺序一维一般从左向右DP机试避坑区分子串连续和子序列可不连续题目读仔细初始化很多人忘记初始化dp数组出现负数、0错误空间能优化就优化一维dp经常只需要保存前一个值数据范围大的时候O(n²)会超时改用二分优化LIS数组下标从0还是从1开始不要混用DP选型速查题目DP转移最大连续子数组dp[i] max(nums[i], dp[i-1]nums[i])LIS最长递增子序列dp[i] max(dp[i], dp[j]1)跳台阶dp[i] dp[i-1]dp[i-2]要不要再来01背包完整样题华为偶尔考二维DP