一道 6-7 年级奥数题

[zungmou]

小智在镇上四处抓宝可梦。每天，他可以向他的收藏中添加 3 只、4 只或 5 只宝可梦，但他不能在连续的两天内添加相同数量的宝可梦。要让他恰好收集到 100 只宝可梦，最少需要多少天？

[itskingname]

这不就是算法里面经典的上楼梯问题吗？每步可以上 3 、4 或 5 级台阶，要上 100 级台阶最少要走几步。倒着算就好了。

[mpfeitech7416]

private static int minDaysToCollect100Pokemons() {
int[][] dp = new int[101][6];
for (int[] row : dp) {
Arrays.fill(row, INF);
}

// 初始化状态
dp[0][3] = dp[0][4] = dp[0][5] = 0;

// 填充 DP 表
for (int i = 0; i <= 100; i++) {
for (int last : new int[]{3, 4, 5}) {
if (dp[i][last] != INF) {
if (i + 3 <= 100 && last != 3) {
dp[i + 3][3] = Math.min(dp[i + 3][3], dp[i][last] + 1);
}
if (i + 4 <= 100 && last != 4) {
dp[i + 4][4] = Math.min(dp[i + 4][4], dp[i][last] + 1);
}
if (i + 5 <= 100 && last != 5) {
dp[i + 5][5] = Math.min(dp[i + 5][5], dp[i][last] + 1);
}
}
}
}
return Math.min(dp[100][3], Math.min(dp[100][4], dp[100][5]));
}

[BeforeTooLate]

@cxwave #6 哈哈，你得思路清奇，建议再想想。

[BeforeTooLate]

@workingpad2 小学奥数啊，你小学得时候看到题目不一定觉得简单

[yishengyongyi]

难道不是 23 么

[cloudzhou]

做了一个小尝试，贪心加回溯：

https://gist.github.com/cloudzhou/a839ba0943bb3e9c65997695a88ef865