823.Binary Trees With Factors 解説

元のページ

leetcode.com

問題

与えられた一意の整数からなる配列 arr があり、各整数 arr[i] は必ず1より大きいものとします。

これらの整数を使用してバイナリツリーを作成し、各整数は任意の回数使用できます。各非葉ノードの値は、その子ノードの値の積でなければなりません。

作成できるバイナリツリーの数を返す関数を実装し、その答えが非常に大きい場合、10⁹ + 7 で割った余りを返します。

解説

有料プランしか見ることができないのでSolutionsを参考して書きました。

アプローチ 1:動的計画法

具体例から見ていきましょう。 [2,4,5,10,20]という配列が当たられたとします。

2,5は子のノードがなく1つの[2]、[5]のバイナリツリーしかつくれません。 4は[4],[2,2]が作成できます。 10のときは[10],[10, 2, 5], [10, 5, 2]となります

表記場二つのみとすると 20のときは[20],[2,10,2,5],[4,5],[5,4],[10,2]となります。 ここで20のとき4,10はさらに複数のバイナリツリーが作成できます。

このため自身の約数のバイナリツリーができる数をあらかじめ求めておく必要があります。

一般化すると バイナリツリーを作成する数を、の約数をとすると以下の式が成り立ちます

] を]のバイナリツリーを作成することができる数とすると

] = ] + ] * ]

これを > となるすべてのに対してがの約数であるか調べてから動的計画法の計算行い が求める答えとなります

アルゴリズム

arrayが配列として与えられていると

1. arrayをソート
2. 1からarray.sizeまでループ。添え字をiとする
3. 1からiまでループ
4. array[j]がarray[i]の約数ならばdp[array[i]] にd[array[j] * dp[array[i] /array[j]]を足す

実装

配列でなく連想配列を使っています。

Rust

use std::{cmp::*, collections::*, *};
impl Solution {
    pub fn num_factored_binary_trees(mut arr: Vec<i32>) -> i32 {
        const modu: i64 = 10_i64.pow(9) + 7;
        let mut dp: HashMap<i32, i64> = HashMap::new();

        arr.sort();

        for i in 0..arr.len() {
            let mut vi = 1;
            for j in 0..i {
                if arr[i] % arr[j] == 0 && dp.contains_key(&(arr[i] / arr[j])) {
                    let vj = *dp.get(&arr[j]).unwrap();
                    let vrm = *dp.get(&(arr[i] / arr[j])).unwrap();
                    vi = (vi + vj * vrm) % modu;
                }
            }
            dp.insert(arr[i], vi);
        }
        (dp.values().sum::<i64>() % modu) as i32
    }
}