Dynamic Programming

• video

基本思路:

首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。

DP Notions

1. Characterize structure of optimal solution
2. Recursively define the value of an optimal solution based on optimal solution of subproblems
3. Compute value of optimal solution
4. Construct an optimal solution from computed information

Longest Palindromic Sequence

palindrome example: radar, t, a, bb, redder

Given: A string X[1...n], n >= 1 Longest palindrome that is a subsequence answer >= 1 length

Example:

character -> carac
underqualified -> defied
turboventilator -> rotator

Strategy:

L(i, j): length of longest palindrome subsequence X[i...j], i <= j

def L(i, j):
    if i == j: return 1
    if X[i] == X[j]: 
        if (i+1 == j): return 2
        else 2+L(i+1, j-1)
    else: return max(L(i+1, j), L(i, j-1))

Time Complexity: O(n^2) with cache

# subproblems x try to solve each subproblem given that smaller ones are solved Look up is O(n)

Optimal BSTs

keys K1, K2, ..., K

Maximize the amount of money when assuming you moving first.

V(i,j): max value we can definitely win if it is our turn and only coins Vi,...,Vj remain

Base Case: V(i,i): just pick Vi V(i,i+1): pick the maximum of the two

V(i,i+2): ???

V(i,j): max{pick Vi, pick Vj} max{range is (i+1,j)+vi, range is (i, j-1)+vj} opponent moves

Solution:

V(i+1,j) subproblem with opponent picking => we are guaranteed min{V(i+1,j-1), V(i+2,j)} opponent picks Vj, or V_{i+1}

Now we want to derive the more general case. dp[i][j] = max( something + v[i], something + v[j]), since we either will pick the i or j coin. The problem now turns to what "something" here will be.

A quick idea may be dp[i][j] = max( dp[i + 1][j] + v[i], dp[i][j - 1] + v[j]), but here dp[i + 1][j] and dp[i][j - 1] are not the values directly available for us, it depends on the move that our opponent make.

Then we assume our opponent is as good as we are and always make optimize move. The worse case is that we will get the minimal value out of all possible situation after our opponent make its move.

so the correct dp formula would be dp[i][j] = max( min (dp[i + 1][j - 1], dp[i + 2][ j]) + v[i], min (dp[i][j - 2], dp[i + 1][ j - 1]) + v[j]}). If we pick i, then our opponent need to deal with subproblem dp[i + 1][j], it either pick from i + 2 or j - 1. Similarly, If we pick j, then our opponent need to deal with subproblem dp[i][j - 1], it either pick from i + 1 or j - 2. We take the worse case into consideration so use min() here.

Time Complexity: O(n^2)*O(1)

class Solution {
    int helper(vector<int>& nums, int s, int e, vector<vector<int>>& mem) {
        if (mem[s][e] != INT_MAX) return mem[s][e];
        if (s == e) return mem[s][e] = nums[s];
        return mem[s][e] = max(nums[s]-helper(nums, s+1, e, mem), nums[e]-helper(nums, s, e-1, mem));
    }
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> mem(n, vector<int>(n, INT_MAX));
        return helper(nums, 0, n-1, mem) >= 0;
    }
};