华为2021实习招聘笔试题
输入输出示例:
5 5 10
3 5 4 2 3
4 5 3 4 3
4 3 5 3 2
2 5 3 3 5
5 3 4 4 1
输出：-1 （无论走哪条路线，都会超过可游玩时间t，所以输出-1）
5 5 30
3 5 4 2 3
4 5 3 4 3
4 3 5 3 2
2 5 3 3 5
5 3 4 4 1
输出：30
思路：此题是leetcode64题的改编题。https://leetcode-cn.com/problems/minimum-path-sum/ 最大（小）路径和
本题在此基础上对最值进行了限制。第一想法，为每个位置维护一个列表，记录到达该位置的所有可能的取值（对本题来说即游玩时间）。优雅一点的实现，即数组增加一维，来维护到达该位置的所有取值。
参考代码：
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int m,n,t;
freopen("input.txt","r",stdin);
cin>>m>>n>>t;
int board[m][n];
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
cin>>board[i][j];
//新增一维k
//dp[i][j][k]表示到达位置(i,j)能否凑出k值
//相当于给每个位置维护了一个vector
int dp[m][n][t+1];
memset(dp,0,sizeof(dp));
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
//起点位置
if(i==0&&j==0){
if(board[i][j]<=t)
dp[i][j][board[i][j]] = 1;
}
//如果是第一行 当前位置只能从左侧到达
else if(i==0){
for(int k=0;k<=t;++k){
if(dp[i][j-1][k] && k+board[i][j]<=t)
dp[i][j][k+board[i][j]] = 1;
}
}
//如果是第一列 当前位置只能从上方到达
else if(j==0){
for(int k=0;k<=t;++k){
if(dp[i-1][j][k] && k+board[i][j]<=t)
dp[i][j][k+board[i][j]] = 1;
}
}
//其他位置(i,j) 可以从(i-1,j)或者(i,j-1)转移过来
else{
for(int k=0;k<=t;++k){
if(dp[i-1][j][k] && k+board[i][j]<=t)
dp[i][j][k+board[i][j]] = 1;
if(dp[i][j-1][k] && k+board[i][j]<=t)
dp[i][j][k+board[i][j]] = 1;
}
}
}
}
int ans = -1;
for(int k=t;k>=0;k--)
//对于出口位置 扫描一遍 返回满足条件的最大值
if(dp[m-1][n-1][k]){
ans = k;
break;
}
cout<<ans<<endl;
return 0;
}
状态压缩dp
1. 旅行商问题(TSP)
以4个城市为例，介绍动态规划模型的构造。城市间距离的邻接矩阵如下：
n = 4
S0 S1 S2 S3
S0 0 2 6 5
S1 2 0 4 4
S2 6 4 0 2
S3 5 4 2 0
思路分析：从初始点出发的周游路线一共(n-1)!条，即另外n-1个点的排列数，通过枚举所有路线来求最小值，时间复杂度显然是O(n!)。假设s0->s1->s2->s3->s0是从s0出发的路径长度最短的简单回路，当s0->s1确定，那么s1->s2->s3->s0是s1通过所有其他点到s0的最短路径。也就是说该问题具有最优子结构。否则将产生矛盾。比如这样两条线路:
s0->s1->s2->s3->s0与s0->s1->s3->s2->s0，总长度最优，则s1->s2->s3->s0必然也是最优，证明了使用动态规划的合理性。
将总回路长度分解有：
length(总回路) = min(length(s0,s1)+length(s1,...s0),length(s0,s2)+length(s2,...s0),length(s0,s3)+length(s3,...s0))
规范化的表达：
d(i,V)表示从i点经过点集V内所有点各一次后回到出发点城市（本例是城市0）的最短距离。
d(i,V') = min{Cik+d(k,V'-{k})} k∈V'
d(k,{}) = Cik (i≠k)
其中Cik表示城市i到城市k的距离。
举个具体点的栗子：
从城市0出发，经过城市1，2，3再回到城市0的最短路径长度为：
L = min{ C01+d(1,{2,3}), C02+d(2,{1,3}), C03+d(3,{1,2}) } 这个式子依赖d(1,{2,3})、d(2,{1,3})、d(3,{2,1})的值，继续拆解得：
d(1, {2, 3})=min{ C12+d(2, {3}), C13+ d(3, {2})}
d(2, {1, 3})=min{ C21+d(1, {3}), C23+ d(3, {1})}
d(3, {1, 2})=min{ C31+d(1, {2}), C32+ d(2, {1})}
继续
d(1, {2})= C12+d(2, {}) d(2, {3})=C23+d(3, {}) d(3, {2})= C32+d(2, {})
d(1, {3})= C13+d(3, {}) d(2, {1})=C21+d(1, {}) d(3, {1})= C31+d(1, {})
到达最小的子问题，可直接求解。
dp[i][j]表示的含义：从点i经过集合j回到出发点(城市0)的最短路径。
状态压缩表现在使用了二进制表示集合。比如点集1、3表示为101==5，点集1、2、3表示为111==7。即
dp[0][{1,2,3}]=dp[0][7] = min(dis[0][1]+dp[1][{2,3}], dis[0][2]+dp[2][{1,3}], dis[0][3]+dp[3][{1,2}])=min(dis[0][1]+dp[1][6],dis[0][2]+dp[2][5],dis[0][3]+dp[3][3])
最后有dp[1][{}]意思就是从1号点出发不经过任何点回到0的最短距离，那么这个距离直接就是dis[1][0].
参考代码：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
// 二维dp表 n行代表n个城市，M列表示M个集合状态
int n = scan.nextInt();
int M = 1<<(n-1);
int[][] dp = new int[n][M];
// 题目给定的两两城市之间的距离
int[][] map = new int[n][n];
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
map[i][j] = scan.nextInt();
}
// 集合为空时 直接计算该城市到0号城市的距离
for(int i=1;i<n;++i)
dp[i][0] = map[i][0];
// 自底向上 从小集合算起
for(int j=1;j<M;++j){
for(int i=0;i<n;++i){
// 第i号城市已在集合中 如dp[1][{1,2}] 不符合 跳过
if(i>0 && ((j>>(i-1))&1)==1)
continue;
// 赋初值
dp[i][j] = Integer.MAX_VALUE;
// 穷举所有情况
for(int k=1;k<n;++k){
//k没有在集合中 则无法选中它用来作为跳板
if(((j>>(k-1))&1)==0)
continue;
// 提取k城市 转移到代价更小的路线中
dp[i][j] = Math.min(dp[i][j],map[i][k]+dp[k][j^(1<<(k-1))]);
}
}
}
System.out.println(dp[0][M-1]);
}
}背包dp
1.换钱使用最少的货币数
#include<bits/stdc++.h>
using namespace std;
int main()
{
// n为货币种数 aim是要换的目标钱数
// 输出使用的最少货币张数
int n,aim;
cin>>n>>aim;
if(aim==0)
{
cout<<0<<endl;
return 0;
}
vector<int>v(n);
for(int i=0;i<n;++i)
cin>>v[i];
// dp第一维表示在使用第i张面值为v[i]的货币，第二维表示要凑的钱数大小
int dp[n+1][aim+1];
// 当所有面值的货币都使用完，只有钱数为0的目标可以凑成，需0张
for(int j=1;j<=aim;++j)
dp[n][j] = -1;
// 依次使用各面值的货币
for(int i=n-1;i>=0;--i)
{
for(int j=0;j<=aim;j++)
{
// 先设置这个钱数凑不成
dp[i][j] = -1;
// 如果在使用当前面值的货币之前已经凑成了，则改为可以凑成
if(dp[i+1][j]!=-1)
dp[i][j] = dp[i+1][j];
// 如果钱数少的可以凑成
if(j-v[i]>=0&&dp[i][j-v[i]]!=-1)
{
// 如果当前位置无效 则改为有效
if(dp[i][j]==-1)
dp[i][j]=dp[i][j-v[i]]+1;
// 否则 取最小
else dp[i][j]=min(dp[i][j],dp[i][j-v[i]]+1);
}
}
}
cout<<dp[0][aim]<<endl;
return 0;
}时间复杂度O(n*aim)。 此外可以进行空间上的优化。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,aim;
cin>>n>>aim;
if(aim==0)
{
cout<<0<<endl;
return 0;
}
vector<int>v(n);
for(int i=0;i<n;++i)
cin>>v[i];
int dp[aim+1];
memset(dp,0,sizeof(dp));
// 未使用任何货币之前，只有钱数为0可以凑成，需要0张。
for(int i=0;i<=aim;++i)
dp[i]=-1;
dp[0] = 0;
// 遍历所有面值的货币v
for(int i=0;i<n;++i)
{
// 凑当前在使用货币面值的钱数 一张即可
dp[v[i]] = 1;
// 只有钱数大于v[i]的位置开始 才受到新面值货币的影响
for(int j=v[i]+1;j<=aim;++j)
{
// 如果之前位置的钱数已经凑成
if(dp[j-v[i]]!=-1)
{
// 当前没凑成 则改成可以凑成
if(dp[j]==-1) dp[j]=dp[j-v[i]]+1;
// 当前位置已经凑成 则取最小
else dp[j] = min(dp[j],dp[j-v[i]]+1);
}
}
}
cout<<dp[aim]<<endl;
return 0;
}线性dp
1.求最长的有效括号长度
思路分析:有效括号必定以右括号)结尾。则有两种情况：若当前s[i]是),s[i-1]是(，即...()的形式，那么dp[i]=dp[i-2]+2;若当前是),s[i-1]是)，形如...))。如果当前)是有效括号的一部分，那么必定需要s[i-dp[i-1]-1]是(才行。即dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
class Solution {
public:
int longestValidParentheses(string s){
if(s.empty()) return 0;
int dp[s.size()];
memset(dp,0,sizeof(dp));
int ans = 0;
for(int i=1;i<s.size();++i)
{
// 有效括号必定以右括号结尾
if(s[i]==')')
{
if(s[i-1]=='(')
{
dp[i] = (i>=2 ? dp[i-2] : 0) + 2;
}
// s[i-1] 是')'
else if( i-dp[i-1]>0 && s[i-dp[i-1]-1]=='(')
{
dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2 >= 0? dp[i-dp[i-1]-2] : 0);
}
}
ans = max(ans,dp[i]);
}
return ans;
}
};
京公网安备 11010502036488号