leetcodeブラシ問題、まとめ、記録、メモ312

leetcode312Burst Balloons
Given  n  balloons, indexed from  0  to  n-1 . Each balloon is painted with a number on it represented by array  nums . You are asked to burst all the balloons. If the you burst balloon  i  you will get  nums[left] * nums[i] * nums[right]  coins. Here  left  and  right  are adjacent indices of  i . After the burst, the  left  and  right  then becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
Note:  (1) You may imagine  nums[-1] = nums[n] = 1 . They are not real therefore you can not burst them. (2) 0 ≤  n  ≤ 500, 0 ≤  nums[i]  ≤ 100
Example:
Given  [3, 1, 5, 8]
Return  167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

この問題は私個人にとってやはり難しいと感じて、分けて治めることと動態計画に対する敏感度が低くて、使うのも拙策で、そこで各種の解答案をめくって、ついに自分の少しの小さい悟りがありました.
まず元の配列の先頭と末尾にそれぞれ2つの値が1の要素を追加し,配列次元数がn+2になる.その後、次元数n+2 x n+2の空の全0の2次元配列が作成されます.
この2次元配列は、result[1][5]のような各セグメントの最大硬貨数を保存するために使用される.すなわち、1番目の電球から5番目の電球までの区間の最大硬貨数を表す.その後、区間の長さlenを定義し、終了点位置startとendを開始する必要があります.最大長さは1からnまで,開始位置は1からn−len+1まで,終了位置も相応に算出できる.このとき、遍歴するたびに、result[start][end]の値を求め、一歩一歩押して、最後の結果result[1][n]を求めるのが区間全体の最大硬貨数です.実は前のステップはすべてよく理解して、最も重要なのは動態計画の繰返し式で、以下のようにします
result[start][end] = max(result[start][end], result[start][i-1] + result[i+1][end] + nums[start-1]*nums[i]*nums[end+1]);
私は最初からこの場所でぼんやりしていて、どういう意味か分かりませんでしたが、それから自分で考えて、理解しました.ここでiはstartとendの間にあり、最後に消灯した電球の位置として仮定し、startとendの間でそれぞれ最後の電球が消滅した位置として選択し、それぞれ値を求め、最大値をresult[start][end]に保存する、すなわち、この区間硬貨の最大数である.このときstart=1,end=4,iはちょうど2まで遍歴していると仮定し,繰返し式によれば,2番目の電球が最後に消滅した場合,求めた硬貨の数はresult[1][1]+result[3][4]+nums[0]*nums[2]*nums[5]であるはずであるが,ここを見ると,区間が1-4,2番目の電球が最後に消滅した場合,まず区間1-1の硬貨の数,区間3-4の硬貨の数,加算しなければならない.そして、先に2程度の電球を消したので、最後に残った左右の両側はnums[0]とnums[5]とnums[2]の積で、加算して、最後に電球2を消した最大の硬貨の数である.次に、最大値を保持する順に巡回します.だから肝心なのは1つのアルゴリズムを理解してやはり自分で絶えず試して、紙の上で絵を書いてこそ最も深い体得があって、とても肝心で、いいでしょう.
編集して、コードを貼るのを忘れました...

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        nums.insert(nums.begin(), 1);
        nums.insert(nums.end(), 1);
        
        vector<vector<int> > result(nums.size(), vector<int>(nums.size(), 0));
        
        int len, start, end;
        for (len = 1; len <= n; ++len)
        {
            for (start = 1; start <= n - len + 1; ++start)
            {
                end = start + len - 1;
                for (int i = start; i <= end; ++i)
                {
                    result[start][end] = max(result[start][end], result[start][i-1] + result[i+1][end] + nums[start-1]*nums[i]*nums[end+1]);
                }
            }
        }
        
        return result[1][n];
    }
};