Rust 版

はじめに

---

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

コード全体

---

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

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

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

基本的な方針としては，triangleの各要素の底からのコストをそれぞれ算出し，底から頂点の順に値を上書きしていく．

class Solution {
public:
  int minimumTotal(vector<vector<int>>& triangle) {
    for (size_t i=triangle.size()-2; i<triangle.size(); --i) {
      for (int j=0; j<triangle[i].size(); ++j) {
        triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
      }
    }
    return triangle[0][0];
  }
};

解説

---

準備

---

class Solution {
public:
  int minimumTotal(vector<vector<int>>& triangle) {

縦ループ（反転）

---

反転したたてのループとは，上からではなく下からのループを指す．

triangle.size()-1ではなくtriangle.size()-2から開始となっているのは，底辺の各要素に対する底からのコストは，自身の値となるためである．

    for (size_t i=triangle.size()-2; i<triangle.size(); --i) {

横ループ

---

ひとつ下の列からの最小コストで上書きする．

      for (int j=0; j<triangle[i].size(); ++j) {
        triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
      }
    }

結果

---

頂点の上書き結果が答えとなる．

    return triangle[0][0];
  }
};

おわりに

---

C++は自由度が高くてイイネ(≧∇≦)b

関数の引数の書き換えで勝手に参照に出来てしまうので，値が上書きされてしまう可能性があり呼び出し側は発狂する・・・？

参考

---