背景
これが解けなかった。
メモ化再帰を知っていればあっさり解ける問題だったが軽く調べてみてrustでの実装が無かったので書いてみたという話
実装
こんな感じ.
何回再帰の底までたどり着いたかカウントするための
グローバル変数が入っている。あとは
メモにハッシュマップを使っている。elseの実装が汚いのなんとかならんか。if false は上と入れ替えると単純な再帰だとどうなるかよくわかる。
static mut c:u32 = 0;
fn f(x:u64,h:&mut HashMap<u64,u64>) -> u64{
if x == 0{
unsafe{c+=1;}
1
}else{
if h.get(&x) != None{
//if false{
*h.get(&x).unwrap()
}else{
let xx = f(x/2,h) + f(x/3,h);
h.entry(x).or_insert(xx);
xx
}
}
}
fn main() {
input!{
n:u64,
}
let mut h:HashMap<u64,u64> = HashMap::new();
println!("{:?}",f(n,&mut h));
//unsafe{println!("{:?}",c);}
}