[2022刷题打卡 2/365]390. 消除游戏

先是题目: 390. 消除游戏

给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

很遗憾, 这道数学题我不会......

就当作时复习go了

今天的解法参考大佬的动态规划-》dfs不记忆化

Java Version

   class Solution {
        public int lastRemaining(int n) {
            return dfs(n);
        }

        private int dfs(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            if (n % 2 != 0) {
                return dfs(n - 1);
            } else {
                return 2 + n - 2 * dfs(n / 2);
            }

        }
    }

Go Version

package January

func lastRemaining(n int) int {
	return dfs(n)
}

func dfs(n int) int {
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	if n%2 != 0 {
		return dfs(n - 1)
	} else {
		return 2 + n - 2*dfs(n/2)
	}
}