C++版

はじめに

---

可変長の２重配列を持つトライアングルと呼ばれる入力の，頂点から底辺へ降りる際の最短距離を求める問題．

コード全体

---

今回は，DP (Dynamic Programming)と呼ばれるものを使って解答を作った．

上から降りていくと，条件分岐の複雑化や最終的な解を取り出すのにO(N)要するので，反転して探索することにした．

図的に表すと，トライアングルの底から頂点へと登っていくコストを加算していき，最後に頂点の値となったものが解となる．

use std::cmp;

impl Solution {
  pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
    let mut old: Vec<i32> = triangle.last().unwrap().to_vec();
    for nums in triangle.iter().rev().skip(1) {
      let mut new = Vec::<i32>::new();
      for (j, num) in nums.iter().enumerate() {
        new.push(num + cmp::min(old[j], old[j+1]));
      }
      old = new;
    }
    old[0]
  }
}

解説

---

準備

---

整数の比較をするためにstd::cmpを利用

use std::cmp;

impl Solution {
  pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {

メモ用配列

---

過去の値をメモする配列を準備

初期値は，底辺の配列．

ループ中に，ひとつ下の列のコストがメモされている．

    let mut old: Vec<i32> = triangle.last().unwrap().to_vec();

縦ループ

---

反転ループ．

Rust のクールな API によって，シンプルに書くことができた．

skip(1)は，底から探索開始するため「底にたどり着くためのコストは各値自身」となるので，そのまま値を用いる．

    for nums in triangle.iter().rev().skip(1) {
      let mut new = Vec::<i32>::new();

横ループ

---

ひとつ下のコスト配列から，自身に到達するための最小コストを算出する．

      for (j, num) in nums.iter().enumerate() {
        new.push(num + cmp::min(old[j], old[j+1]));
      }

メモの更新

---

一つ列を上がる前に，oldを更新する．

      old = new;
    }

結果

---

最終的に，oldは要素数1の配列となり，その値が答えとなる．

つまり，頂点に到達するための最小コストが最後に残る．

    old[0]
  }
}

おわりに

---

Rust のiter()や，rev(), skip()などの API の便利さが際立った．

その一方で，C++のように値の変更を簡単に行えないという点が，別でメモ用の配列を準備することになり，アルゴリズムとしての綺麗さが損なわれる結果となった（Rust が原因というよりは，自分の知識不足が原因かもしれないが）．これは，入力側がmutを与える必要があるという点と LeetCode の制約によるものだと思うので，実際のシステム開発においてはむしろ開発者の助けになるはずである．

参考

---