dp_rust

Rust 过程宏，用于将 memoization 应用到纯函数。

此 crate 仍处于 beta 版。如果可能，请报告问题。

用法

有关 memoization 的解释，请参阅说明

实现 memoization 简单，但需要一些时间和添加样板代码。

dp 属性

只需将原始 fn 和在开头添加 #[dp] 即可。

fn main(){
  assert_eq!(102334155, fib(40));
}

#[dp]
fn fib(n: i32) -> i32{
  if n < 2{
    return n;
  }
  (fib(n-1) + fib(n-2)) % 1_000_000_007
}

函数不能在 impl 内部。

在非纯函数上使用 dp 宏是未定义行为。注意，纯不意味着 const，例如，尽管在 const 中禁止循环，但您仍然可以使用循环。

所有参数以及输出都必须实现 Clone。

额外参数

如果需要，可以使用 #[dp_extra] 属性包含额外的不可变参数。

fn main(){
  assert_eq!(
    knapsack(vec![3, 4, 5, 6, 10], vec![2, 3, 4, 5, 9], 5, 10),
    13
  );
}

#[dp]
#[dp_extra(values: Vec<i32>, weights: Vec<i32>)]
fn knapsack(n: usize, k: i32){
  if n == 0 {
    return 0;
  }
  let mut ans = knapsack(n - 1, k);
  if k >= weights[n - 1] {
    ans = std::cmp::max(ans, knapsack(n - 1, k - weights[n - 1]) + values[n - 1]);
  }
  return ans;

}

顺序是首先所有额外参数，然后是按出现顺序的所有函数参数。

默认参数

#[dp_default] 属性允许您删除最终函数中应默认的辅助参数。

use std::cmp::min;

fn main(){
  assert_eq!(edit_distance("movie", "love"), 2);
}


#[dp]
#[dp_extra(a: String, b: String)]
#[dp_default(i=a.len(); j=b.len())]
fn edit_distance(i: usize, j: usize) -> usize{
  if i == 0{
    return j;
  }
  if j == 0{
    return i;
  }
  let mut ans = min(edit_distance(i-1, j), edit_distance(i, j-1))+1;
  if a.as_bytes()[i-1] == b.as_bytes()[j-1]{
    ans = min(ans, edit_distance(i-1, j-1));
  }
  else{
    ans = min(ans, edit_distance(i-1, j-1)+1);
  }
  return ans;
}

如上所示，可以使用默认参数 n = values.len() 实现背包问题。