前几天遇到一道题目，题目的大意是这样的：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

public 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]

自顶向下的动态规划

import 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;
    }
}

自顶向上的动态规划 + 滚动数组

import 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。
这其实也是一个经验点，当你拿到很一般的问题时，尝试先解决特定问题，这样就有机会猜出来最一般问题的解决办法。

import 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。

总结

本文从一道题开始，讲述遇见没写过的题，应该去如何思考。即：

分析时，抓住特点，从而尝试用对应的解题方法
使用制表法来求解递归问题以及简单动态的递推公式
遇到特别一般问题，应该尝试先解决特定问题，通过特定问题来解决一般问题

但这都是下策，因为成功率确实远不及这道题你刷过。

wangjie_fourth

以一道题来思考如何写算法题