想了一个递回DP
因为这是一个取或不取的问题 很适用递回法
基本型态会是 f(n) = g(f(n-1), f(n-2), ... ) 这样 g()通常是min或sum或if-else
可以系统化来写这3个步骤:
1. 写递回式
2. 写终止条件
3. 写查表
以这题来说 可以写一个递回 rec(0,0,0) :
// pos:第几位, prev:上次的数字, acc:目前取几位了
int rec(int pos, int prev, int acc) {
// 递回式
int ret = 0;
for (int i = 0; i < 10; ++i) {
if (i >= prev)
ret += rec(pos+1, i, acc+1); // 要这位数
else
ret += rec(pos+1, prev, acc); // 不要这位数
}
return ret;
}
那么再来就是终止条件 我想了3个:
int rec(int pos, int prev, int acc) {
// 终止条件
if (acc > 4) return 0; // 取超过了
if (pos > 6) return acc == 4; // 到底了是否刚好取到4个
if ((7 - pos) + acc < 4) return 0; // 不够取了
// 递回式
...
}
到这应该就可以运作了 以c++ code来说其实已经够快
不过这样还没用到查表
于是直接把整个rec的参数拿来当key:
struct S {
int pos, prev, acc;
bool operator<(const S &o) const {
if (pos != o.pos) return pos < o.pos;
if (prev != o.prev) return prev < o.prev;
return acc < o.acc;
}
};
static map<S, int> cache;
int rec(int pos, int prev, int acc) {
// 终止条件
...
// 查表
auto iter = cache.find({pos,prev,acc});
if (iter != cache.end()) return iter->second;
// 递回式
...
cache[{pos,prev,acc}] = ret;
return ret;
}
这样就完成啦
答案是2027025 (希望是对的)
时间的话 在我电脑上直接暴力解是0.75秒 纯递回是0.063 加DP是0.017
看起来似乎合理
※ 引述《applebeing (苹果人)》之铭言：
: 求职时线上测验的问题，有算出解答，但觉得应该有更好的解法，
: 向各位版友请教解题想法。
: 问题如下：
: 一个七位数的数字，从第七位到个位数的顺序开始比对。
: 若当前位数的值，不小于曾出现过的数的最大值，就记录起来。
: 请问纪录结果为四个数字的可能组合数有几组？
: 例：
: 2334849 - 由左至右
: 第一位数 2 加入纪录
: 第二位数 3 大于等于2，加入纪录
: 第三位数 3 大于等于3，加入纪录
: 第四位数 4 大于等于3，加入纪录
: 第五位数 8 大于等于4，加入纪录
: 第六位数 4 不纪录
: 第七位数 9 大于等于8，加入纪录
: 纪录结果为 6
: 6429748 - 纪录 69 （2个数）
: 4629889 - 纪录 4699（4个数）
: 各位数可以为 0，例如 0001234、0007899 也符合要求。
: 我用循环跑 1~一千万涵盖七位数，每个数字都检查纪录结果，得出组数。
: 跑了五分多钟，很笨也很没有效率。
: 想请问是否有更效率的解题方式？
: 请大家指教，感谢！