An O(n^2) DP Solution, Quite Hard.


  • 15
    A

    Algorithm description: http://artofproblemsolving.com/community/c296841h1273742

    #include <vector>
    #include <deque>
    using namespace std;
    
    class Solution {
    public:
        int getMoneyAmount(int n) {
            vector<vector<int>> u(n + 2, vector<int>(n + 2));
            for (int b = 2; b <= n; ++b) {
                int k0 = b - 1;
                deque<pair<int, int>> v;
                for (int a = b - 1; a; --a) {
                    while (u[a][k0 - 1] > u[k0 + 1][b]) {
                        if (!v.empty() && v.front().second == k0) v.pop_front();
                        --k0;
                    }
                    int vn = a + u[a + 1][b];
                    while (!v.empty() && vn < v.back().first) v.pop_back();
                    v.emplace_back(vn, a);
                    int u1 = u[a][k0] + k0 + 1;
                    int u2 = v.front().first;
                    u[a][b] = u1 < u2 ? u1 : u2;
                }
            }
            return u[1][n];
        }
    };
    

  • 0
    M

    Very beautiful analysis and optimization! Brilliant!

    But very, very hard for most people I think.

    btw, 前排ym zkw大神。


  • 1
    K

    Fantastic algorithm. Though it's hard to swallow, the idea is worth reading and implementing.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.