世界杯主题曲歌词 / 2025-11-17 08:43:21
前几天遇到一道题目，题目的大意是这样的：10个人围一圈，数到3或者3的倍数就被踢出，请问最后一个人是在刚开始排序的位置是多少？
从一道题开始先说这道题的背景是啥：这其实是LeetCode上的一个算法题，有一个对应的历史故事，也就是约瑟夫问题，好奇的同学可以自行百度了解。我们只看拿到这种题目到底应该怎么思考。如果你没刷过这道题，在了解题目后，就应该在草稿本上开始推算这个过程。每到3就踢出，然后再数到3，又退出，这种重复直接最后一个人的过程，是不是很像递归？这个时候，就应该想应该把什么状态作为一个函数。这里我们作为上帝视角，假设你正好想对了状态：即f(num, 3)表示有num个人，每数到3就踢出一个人之后，返回最后一个人在刚开始的位置。
你这时在想，那要是我这个状态一开始想错了咋办？凉拌。这种就跟解数学题一样，如果思路错了，很难再纠正过来。
这个时候你开始在草稿纸上开始写了：
num
1
2
3
4
5
6
7
8
9
10
k
3
3
3
3
3
3
3
3
3
3
result
1
2
2
1
4
1
4
7
1
4
这时候开始小学算术题了，让我们开始找规律吧。如果你恰巧发现f(num) = [ f(num - 1) + 3] % num == 0 ? num : [ f(num - 1) + 3] % num的话，恭喜你，你已经写出来打部分了。这时候，归纳一下：
f(0) = 1
f(num) = (f(num - 1) + 3) % num == 0 ? num : (f(num - 1) + 3) % num
12345678910public static void main(String[] args) { System.out.println(cal(10));}public static int cal(int num) { if (num == 1) { return 1; } return (cal(num - 1) + 3) % num == 0 ? num : (cal(num - 1) + 3) % num;}
从之前的经验可以知道，一般递归题目都是可以用动态规划来写的，那我们再动态规划的思路来写。
动态规划的写法写动态规划的四大步骤：
定义状态：dp[n]，自然就是n个人每数到3就踢出，最后剩的那个人在刚开始的位置
状态转移：dp[n] = (dp[n - 1] + 3) % n == 0 ? n : (dp[n - 1] + 3) % n
初始条件：dp[1] = 1
求最优解：dp[n]
自顶向下的动态规划1234567891011121314151617181920212223242526272829import java.util.Arrays;public class Demo { public static void main(String[] args) { System.out.println(cal(10)); } private static int cal(int num) { if (num < 0) { return -1; } // 定义状态 int[] dp = new int[num + 1]; Arrays.fill(dp, -1); dp[0] = 0; dp[1] = 1; return calHelper(dp, num); } private static int calHelper(int[] dp, int i) { if (dp[i] != -1) { return dp[i]; } int result = (calHelper(dp, i - 1) + 3) % i == 0 ? i : (calHelper(dp, i - 1) + 3) % i; dp[i] = result; return result; }}
自顶向上的动态规划 + 滚动数组123456789101112131415161718192021222324import java.util.Arrays;public class Demo { public static void main(String[] args) { System.out.println(cal(10)); } private static int cal(int num) { if (num < 0) { return -1; } // 定义状态 int[] dp = new int[2]; Arrays.fill(dp, -1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= num; i++) { dp[i % 2] = (dp[(i - 1) % 2] + 3) % i == 0 ? i : (dp[(i - 1) % 2] + 3) % i; } return dp[num % 2]; }}
扩展到最一般的情况最一般的情况就是，有num个人，每轮到target时，他就被踢出，问最后剩下的那个人在刚开始的位置是多少。这也是LeetCode的原题。https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/description/
其实你看上面那个递推公式：f(num) = (f(num - 1) + 3) % num == 0 ? num : (f(num - 1) + 3) % num，就很容易想到把3替换成target，即：f(num) = (f(num - 1) + target) % num == 0 ? num : (f(num - 1) + target) % num。这其实也是一个经验点，当你拿到很一般的问题时，尝试先解决特定问题，这样就有机会猜出来最一般问题的解决办法。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.util.Arrays;public class Demo { public static void main(String[] args) { System.out.println(cal01(10, 3)); System.out.println(cal02(10, 3)); } private static int cal01(int num, int target) { if (num < 0 || target <= 0) { return -1; } // 定义状态 int[] dp = new int[num + 1]; Arrays.fill(dp, -1); dp[0] = 0; dp[1] = 1; return cal01Helper(dp, num, target); } private static int cal01Helper(int[] dp, int i, int target) { if (dp[i] != -1) { return dp[i]; } int result = (cal01Helper(dp, i - 1, target) + target) % i == 0 ? i : (cal01Helper(dp, i - 1, target) + target) % i; dp[i] = result; return result; } private static int cal02(int num, int target) { if (num < 0 || target <= 0) { return -1; } // 定义状态 int[] dp = new int[2]; Arrays.fill(dp, -1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= num; i++) { dp[i % 2] = (dp[(i - 1) % 2] + target) % i == 0 ? i : (dp[(i - 1) % 2] + target) % i; } return dp[num % 2]; }}
至此都是我们在答题的应试技巧，那这个问题的递归方程到底是咋得出来呢？
递推公式求解很详细的推导可以看李永乐老师的讲解，非常容易理解。https://www.youtube.com/watch?v=Yeh1_2GyS5s&t=871s
其中关键点是：当num个人在玩数到target就退出时，当第一次数到target时，问题规模就变成f(num - 1)，而f(num)、f(num - 1)俩个问题的答案最后其实是同一个人；也就意味着f(num)、f(num - 1)之间肯定有一个公式。当第一次数到target时，也就是问题规模变成num - 1时，我们将num - 1重新编号。即：
原来的target + 1，变成1，也就是target + 1 - target
原来的target + 2，变成2，也就是target + 2 - target
…
而原来的1号，按照上面的逻辑应该变成1 - target，而这明显是负数，所以到了一定程度就需要取余。也就是我们得出来的递推公式：f(num) = (f(num - 1) + target) % num == 0 ? num : (f(num - 1) + target) % num。
总结本文从一道题开始，讲述遇见没写过的题，应该去如何思考。即：
分析时，抓住特点，从而尝试用对应的解题方法
使用制表法来求解递归问题以及简单动态的递推公式
遇到特别一般问题，应该尝试先解决特定问题，通过特定问题来解决一般问题
但这都是下策，因为成功率确实远不及这道题你刷过。
玫瑰金哪种颜色好看(玫瑰金颜色哪种好看？)cf穿越火线一把盘龙加多少子弹