我正在尝试为这个问题设计出一种合理的算法： 假设我们有许多地点，我们知道每对地点之间的距离。每个地点还有一个分数。目标是在不超过给定距离的情况下从起始位置到达目标位置时最大化总分数。 这是一个简单的例子：起始位置：C，目标位置：B，给定距离：45 解决方案：经过C-A-B路线，得到9分。...

在一次面试中，我被问到这个问题：给定一些正整数数组s，找到最长的子数组长度，使得其所有值的总和小于或等于某个正整数k。每个输入始终至少有一个解决方案。该数组不是循环的。 我开始编写一个动态规划的解决方案，通过从0到k逐渐找到越来越大的最大长度。 下面是我的Python代码，其中有一个错误，...

这个问题是在Google的编程面试中提出的。我想到了两种方法： 找到所有长度为n的子序列，计算两个元素的和并检查它是否等于k。如果是，则打印Yes，否则继续搜索。这是一种暴力的方法。 将数组按非递减顺序排序。然后从其右侧开始遍历数组。假设我们有一个已排序的数组{3,5,7,10}，我们想让...

给定下面所示的手机按键： Given a phone keypad as shown below:1 2 3 4 5 6 7 8 9 0 从数字1开始，按照象棋游戏中马的移动方式，可以形成多少个不同的10位数字？例如，如果我们在数字1处，则下一个数字可以是6或8；如果我们在数字6处，则下...

假设 array[N] 为一个由 N 个非负数值组成的数组。我们需要递归地将该数组分成两个子数组，使每个子数组的最小和达到最大。解决方案可以通过以下递归函数进行描述： 我们要计算 opt[0][N-1]。 假设 c[x][y] 表示从索引 x 到索引 y（包括两端）的 array[i]...

你在一条线上有N个警卫，每个警卫都要求你支付一定数量的硬币。只有当你到达一个警卫前已经支付的硬币总数小于他的要求时，你才可以跳过支付该警卫。找出你穿过所有警卫所需花费的最少硬币数量。 我认为这是一个动态规划问题，但我想不出一个公式。另一种方法是在答案上进行二进制搜索，但如何验证硬币数量是否是...

我在面试中遇到了以下问题： 给定一个有N个阶梯的楼梯，你可以每次走1步或2步。输出从底部到顶部的所有可能方式。 例如：N = 3 Output : 1 1 1 1 2 2 1 在面试时，我只是建议使用动态规划。 S(n) = S(n-1) +1 或者 S(n) = S(n...

有一个由nxn方阵表示的岛屿。 岛上的人站在任何给定坐标（x，y）处。他可以向任何方向移动一步：向右，向左，向上，向下。如果他走出岛屿，他就会死亡。 将岛屿表示为（0,0）到（n-1，n-1）（即nxn矩阵），人站在给定坐标（x，y）。他被允许在岛上移动n步（沿矩阵）。在他走完n步后，他死亡...

我遇到了一个有趣的算法问题： 给定一个整数数组，找出该数组中的无序对数量，例如对于{1, 3, 2}，答案为1，因为{3, 2}是无序的；对于数组{3, 2, 1}，答案为3，因为{3, 2}，{3, 1}，{2, 1}都是无序的。 显然，这个问题可以通过O(n^2)的暴力解法或枚举所有可...

我快要实现我的 Needleman-Wunsch 算法，但是我不确定如何处理一个特殊情况的回溯。我们重新计算得分矩阵以便重构序列（即最长路径）。问题出在当右下角的得分不在匹配矩阵里，而是在插入列矩阵里时（这意味着回溯出来的序列应该有一个插入）。这些序列以 a2m 格式记录，其中序列中的插入用小...