整数拆分问题。提交完发现,大家这的都很不好,感觉我写的是最好的(
其实我也是上维基抄的。但是发现这个写法是真的聪明。

其实就是求分割函数P(n)的值。
根据公式Pk(n)={1..k}Pk(n-k)可以得到第一种解法。
这个公式是能推导出来的。简单来说就是Pk(n) = Pk(n+k),相当于把把n+k个石头放k个罐子里,其中可以先放k个进去,这样就是一个罐子一个石头,剩下的就是P(n)。

fn partitions(n: isize) -> isize { //Solution 1
    let len = n as usize;
    let mut v = vec![0isize; len+1];
    v[0] = 1;
    for i in 1usize..len+1 {
        for j in i..len+1 {i
            v[j] += v[j - i];
        }
    }
    for i in &v{
        print!("{} ",i);
    }
    v[len]
}

根据公式Pn = Pn+Pn-k可以得到解法二。
具体见整数拆分文章
这个公式的证明

fn partitions(n: isize) -> isize {//DP Solution 2
    let len = n as usize;
    let mut v = vec![vec![0isize; len + 1]; len + 1];
    for n in 0..len+1 {
        for k in 0..len+1{
            if n == 0 || k == 0 { v[n][k] = 0; }
            else if n == 1 || k == 1 { v[n][k] = 1; }
            else if n < k { v[n][k] = v[n][n]; }
            else if n == k { v[n][k] = v[n][k - 1] + 1; }
            else { v[n][k] = v[n][k - 1] + v[n - k][k]; }
        }
    }
    v[len][len]
}

其实还能有解法三:
可以用生成函数来做。但是没有DP简单。

一些资料:
整数拆分PPT
维基百科

标签: none

添加新评论