Leetcode (312) Burst Balloons

6126 ワード
lettecode
Leetcode (312) Burst 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
  • 題意:一組の数字を与え、数字の順序を変えない場合、隣接する3つの数を乗算し、1つの積を得ると同時に、中間のその数を配列から削除し、配列中の数字の前後順は変わらない.このような操作(配列の先頭と末尾にそれぞれ1つずつあることが想像できる)を絶えず行い,このような操作が積の和の最大値をどれだけ大きくするかを求める.
  • 考え方:
  • 直観的な考え方で、コンピュータの高速演算能力を利用して、暴力的に解く.しかし,暴力的に配列の各桁を列挙して再帰的に解くと,削除した数字が真ん中であれば,配列を前後の2つの部分に分けてそれぞれ計算するため,アルゴリズムの複雑さの繰返し式は約
    F(n)=∑i=1nF(i−1)+F(n−i−1)
    ,解くと必然的に指数級のアルゴリズムの複雑さである.
  • 式を観察すると,各位置を列挙した後,実際には長い式を短い式に分けて計算することを目的とした分治思想であることがわかる.しかし,列挙された成分が含まれているため,完全な分治アルゴリズムの運用とは言えない.
  • 一方、このような列挙を想像して再帰し、いくつかの再帰樹(再帰森林==)に展開すると、実際には多くの分岐が全く同じであるが、アルゴリズムの過程で何度も計算し、さらにフィボナッチ数の再帰計算方法を思い出すと、同じ問題に直面し、解決方法も簡単である.計算した数を覚えておいて、使うときに計算を繰り返すのを避けることができます.実は、これは空間で時間を変える記憶化検索方法です.

    • したがって,
  • を加算すると,アルゴリズムの複雑度の再帰式は次のように書き換えることができる.
    Findex(n)=maxi=1nFindex(i−1)+Findex+i+1(n−i−1)
  • アルゴリズムの複雑さの面では,再帰森林を考慮し,約
    O(n3)
    (たぶんね...)1 sなんとか過ごせる...

    • class Solution {
private:
    int a[1000][1000];
    int daq(vector<int>&nums,int l , int r)
    {
        if (a[l][r]!=-1) return a[l][r];
        int ans=0;
        for (int mid=l+1;midreturn ans;
    }
public:
    int maxCoins(vector<int>& nums) {
        memset(a,-1,sizeof(a));
        vector<int> coins;
        coins.push_back(1);
        for (auto item:nums) coins.push_back(item);
        coins.push_back(1);
        return daq(coins,0,coins.size()-1);
    }
};
  • もう一つの考え方:
  • 記憶化探索に言及した以上、このようなアルゴリズムは、動的計画に変換する問題で解決される可能性が高いとともに、記憶化探索アルゴリズムは再帰(以上のように)を用いることが多いため、再帰を用いない動的計画方法には一般的に速度的に及ばないが、このような記憶化探索方法のため、分治の考え方によっては、実は短くて正確率の高い解決方法をすぐに書くことができて、これは1種の優位性で、最適化の方向の1つは動的な計画に転化して解決しました.
  • 次に動的計画の状態遷移方程式を考慮し、記憶化探索はトップダウンのプロセスであり、動的計画は状態の遷移を保証しなければならないことに注意し、ボトムアップのプロセス、すなわち解のサブ配列長は1から元の配列長までである.すると、方程式が得られます.
    dpfrom,to=maxtoi=fromdpfrom,i−1+coinsleft−1∗coinsi∗coinsright+1+dpi+1,to
    (書き方が乱れていて、コードが直感的です.ただし、1枚持ち上げると1つのスライダが配列の先頭から後ろにスライドすることに相当するので、真ん中で切断された位置の数は、スライダの先頭の数とスライダの末尾の数に乗算すべきで、切断の前後ではありません)
  • アルゴリズムの複雑さの面では依然として
    O(n3)
    ただし、再帰を除いて最適化効果は良いはずです.

    • class Solution {
public:
    int maxCoins(vector<int>& nums) {
        memset(dp, 0, sizeof(dp));
        int n = nums.size();
        vector<int> coins;
        coins.push_back(1);
        for (auto coin: nums) coins.push_back(coin);
        coins.push_back(1);
        for (int len=1;len<=n;++len)
        {
            for (int from=1;from<=n-len+1;from++)
            {
                int to=from+len-1;
                for (int del=from;del<=to;++del)
                {
                    dp[from][to] = max(dp[from][to], dp[from][del-1]+coins[from-1]*coins[del]*coins[to+1]+dp[del+1][to]);
                }
            }
        }
        return dp[1][n];
    }
private:
#define MAXN 500+5
    int dp[MAXN][MAXN];
};
    Java多重サイクルアルゴリズムの問題:(九九乗算表、平行四角形の印刷、中空菱形の印刷、菱形の印刷、レンガの運搬問題、フィボナッチ数列、サルが桃を食べる問題、回文数、1!+2!+...+20!)
    Leetcode: 207. Course Schedule