滴滴8.26笔试

60分选择，40分编程
编程题：
题目一：最少操作让数组首位最大

题意
给定一个长度为 n 的数组 vec，可以进行如下操作：
从数组中第 2 个到最后一个元素中选择一个元素 x。
将 x 的一半（向下取整）加到数组的第一个元素 vec[0] 上，同时更新 x = x - val。
重复操作，直到 vec[0] 大于等于数组中其他所有元素。
求最少需要多少次操作。

解法
每次操作选择当前 最大元素，这样能最快提高首元素。
循环直到首元素大于等于剩余元素即可。

题目二：宫殿问题拿宝物问题

大致题意
从左上角 (0,0) 出发移动到右下角 (n-1,n-1)，每步只能向右或向下移动。每个格子可以选择 拿 或 不拿，移动规则如下：
横向向右移动：必须拿当前格子才能向右走。
纵向向下移动：必须不拿当前格子才能向下走。
目标是选择路径和格子，使 总数值最大。

解法
动态规划：
定义状态：
dp[i][j][0]：到 (i,j) 且拿当前格子的最大值
dp[i][j][1]：到 (i,j) 且不拿当前格子的最大值

状态转移：
dp[i][j][0] = max(dp[i][j-1][0], dp[i-1][j][1]) + grid[i][j];
dp[i][j][1] = max(dp[i][j-1][0], dp[i-1][j][1]);

初始化：
dp[0][0][0] = grid[0][0];
dp[0][0][1] = 0;
for(int i = 1;i < n; ++i){
        dp[0][i][0] = dp[0][i-1][0] + grid[0][i];
        dp[0][i][1] = dp[0][i-1][0];
        result = max(result,(max(dp[0][i][0],dp[0][i][1])));
}

for(int i = 1;i < n; ++i){
        dp[i][0][0] = dp[i-1][0][1] + grid[i][0];
        dp[i][0][1] = dp[i-1][0][1];
        result = max(result,(max(dp[i][0][0],dp[i][0][1])));
}
#笔试##滴滴#