Leetcode刷題學習筆記–Dynamic Programming

Introduction

可以從前一個狀態推展到目前的狀態?
起始狀態是什麼?

Problems

123. Best Time to Buy and Sell Stock III

一開始我使用暴力破解，但是時間效率不是很好。




















class Solution {
    enum st{buy, sell};
    int helper(vector<int>& prices, int idx, int tr, int prev) {
        if(idx == prices.size() || tr == 2) return 0;
        if(~mem[idx][tr][prev]) return mem[idx][tr][prev];
        int donothing = helper(prices, idx + 1, tr, prev);
        int dotrans;
        if(prev == sell) dotrans = helper(prices, idx + 1, tr, buy) - prices[idx]; // buy
        else dotrans = helper(prices, idx + 1, tr +
         1, sell) + prices[idx];  // sell
        return mem[idx][tr][prev] = max(dotrans, donothing);
    }
    vector<vector<vector<int>>> mem;
public:
    int maxProfit(vector<int>& prices) {
        int sz = prices.size();
        mem.resize(sz, vector<vector<int>>(2, vector<int>(2, -1)));
        return helper(prices, 0, 0, sell);
    }
};

根據官方的解答。這個題目會限制最多兩次，是因為我們可以退化成一次。

如果是一次的話，就是一直找自己前面的最小值。

兩次的意思是，你可以把vector切成前半部和後半部，分別找出最大的profit。

























class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sz = prices.size();
        if(sz <= 1) return 0;
        int leftMin = prices[0];
        int rightMax = prices[sz - 1];

        vector<int> bwd(sz), fwd(sz + 1);
        // 站在i的位置，往後看，會得到的最大profit
        for(int i = 1; i < sz; ++i) {
            bwd[i] = max(bwd[i - 1], prices[i] - leftMin);
            leftMin = min(leftMin, prices[i]);
        }
        // 站在j的位置，往前看，會得到的最大profit
        for(int j = sz - 2; j >= 0; --j) {
            fwd[j] = max(fwd[j + 1], rightMax - prices[j]);
            rightMax = max(rightMax, prices[j]);
        }
        int ans{0};
        for(int i = 0; i < sz; ++i)
            ans = max(ans, bwd[i] + fwd[i + 1]);
        return ans;
    }
};

官方的另一種更optimal的想法是，把第一次得到的profit當成是下一次price價格減少。















class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int t1min = 1e5, t1prof{0}, t2min = 1e5, t2prof{0};
        for(auto& p : prices) {
            t1min = min(t1min, p);
            t1prof = max(t1prof, p - t1min);
            // 因為從t1賺的錢，等於是第二次交易，買入價錢減少
            t2min = min(t2min, p - t1prof); 
            t2prof = max(t2prof, p - t2min);
        }

        return t2prof;
    }
};

1125. Smallest Sufficient Team

參考lee215大的解答。

這題很棒，對DP會有更深的理解。必做。

當選中第i個people的時候，如果把第i個人加入任一個team都會使整體的skill發生變化。

但是第i個人加入的前提是，加入後的人數比加入前的人數還要少。


























class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = req_skills.size();
        unordered_map<string, int> shift;
        for(int i = 0; i < req_skills.size(); ++i)
            shift[req_skills[i]] = i;
        // 選中的team所有的skill，最小的team
        unordered_map<int, vector<int>> m;
        // 避免hash collision
        m.reserve(1 << n);
        for(int i = 0; i < people.size(); ++i) {
            int skill{0};
            for(auto& s : people[i]) skill |= 1　<< shift[s];
            for(auto& ref : m) {
                int comb = ref.first | skill;
                if(!m.count(comb) || m[comb].size() > m[ref.first].size() + 1) {
                    m[comb] = m[ref.first];
                    m[comb].push_back(i);
                }
            }
            m[skill] = {i};
        }
        return m[(1 << n) - 1];    
    }
};

1908. Game of Nim

給你一個vector<int> piles，讓alice和bob輪流玩這個遊戲，每次可以從任意非零的stack中移除最少1個最多全部piles[i]，不能移動的那個palyer就是輸。返回alice使否會贏。這邊的前提是player都是optimal，也就是palyer會選對自己最有利的狀態。

這題算是萬用題。怎麼說。因為任何題目都可以使用暴力破解，也就是列舉所有的可能性。最後再透過memorization來降低複雜度。

這邊的暴力破解就是列舉所以可能的state，一個一個去嘗試，直到有結果。

因為player是optimal的，如果你是player一定會選一個對自己最有利的狀況，也就是會下一手讓對手沒機會贏的狀態。也就是這個nextState對手沒機會贏。

isNextPlayerWin(vector<int>& nextState)定義為，使用nextState這個狀態，對方是否有機會贏。只要一有機會就是return true。因為這樣才能判斷是否是一定可以贏的狀態。






























class Solution {
    string getKey(const vector<int>& piles) {
        ostringstream oss;
        for(auto& n : piles) oss << n << "-";
        return oss.str();
    }
    bool isNextPlayerWin(vector<int>& piles) {
        string key = getKey(piles);
        if(m.count(key)) return m[key];
        for(int i = 0; i < piles.size(); ++i) {
            for(int j = 1; j <= piles[i]; ++j) {
                vector<int> nextState(piles);
                nextState[i] -= j;
                sort(nextState.begin(), nextState.end()); // 排序很重要，避免重複的計算
                if(!isNextPlayerWin(nextState)) { //nextState 對方絕對不會贏，就會採取這個策略，
                                                // 因為選手是optimal
                    return m[key] = true;
                }
            }
        }
        // 沒有一種狀態是"一定"會贏的，所以return false
        return m[key] = false;
    }
    unordered_map<string, bool> m;
public:
    bool nimGame(vector<int>& piles) {
        m[getKey(vector<int>(piles.size()))] = 0;
        return isNextPlayerWin(piles); // the first Next Player is Alice
    }
};

96. Unique Binary Search Trees(Medium)

給定一個數字n，則1~n之間可以組成多少個Binary Search Tree.首先Binary search tree的定義是:

左邊的BTS一定都比root還小。
右邊的BTS一定都比root還大。

n = 1時，結果為1。
n = 2時，有兩個數字[1,2]，當1為root時，2只能為右邊node。當
2為root時，1只能為左邊node，所以結果為2。
n = 3時，有三個數字[1,2,3]，
當1為root時，[]左邊子樹沒有，[2,3]的排列為右邊子樹。
當2為root時，[1]為左邊子樹， [3]為右邊子樹。
當3為root時，[1,2]的排列左邊子樹，[]右邊子樹沒有。
可以看出規律，[左邊子樹個數，右邊子樹個數]
dp[3] = [0, 2] + [1, 1] + [2, 0]
因為左右兩邊相乘的關係，所以dp[0] = 1。










int numTrees(int n) {        
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for(int i = 1; i < n + 1; ++i) {
        for(int j = 0; j < i; ++j)
            dp[i] += dp[j] * dp[i - 1 - j];
    }
        
    return dp.back();
}

368. Largest Divisible Subset(Medium)

給你一個vector<int> nums，找出最大的subset滿足，任兩個數都是倍數關係。並且輸出這個subset。
例如 : nums = [1, 2, 3];可以得到兩個subset[1, 2]和[1, 3]，其中1和3為倍數關係，1和2為倍數關係。

解題思路:

先排序，這樣只需要找比自己小的數字即可。

使用DP，可以算出最大的subset。

如果還要輸出subset內容，就要另外一個vector來記錄前一個節點。

































vector<int> largestDivisibleSubset(vector<int>& nums) {
    auto n = nums.size();
    if (n == 1) return nums; // 只有一個不用計算直接return
    sort(nums.begin(), nums.end()); // 排序
    vector<int> dp(n, 1);
    vector<int> idx(n, -1);
    int maxidx{0};
    int maxlength{0};
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < i; ++j) { // 只找比i還小的數
            if(nums[i] % nums[j] == 0) { // 倍數關係
                if(dp[j] + 1 > dp[i]) { // 比現在還大
                    dp[i] = dp[j] + 1;
                    idx[i] = j;    // 紀錄前一個node
                }
            }
        }
        if(dp[i] > maxlength) { //找出最大subset
            maxlength = dp[i];
            maxidx = i;
        }
    }
        
    vector<int> ans;
    ans.push_back(nums[maxidx]);
    int p = idx[maxidx];
    while(p != -1) {
        ans.push_back(nums[p]);
        p = idx[p];
    }
        
    return ans;
}

152. Maximum Product Subarray(Medium)

給你一個vector<int>找出，subarray中相乘數字最大的值。

subarray為連續的element.

最大值 = (負數) * (負最大值) or (正數) * (正最大值)

必須同時記錄"負最大值"和"正最大值"。













int maxProduct(vector<int>& nums) {
    auto n = nums.size();
    int curr_max, curr_min, maxval;
    maxval = curr_max = curr_min = nums[0];
        
    for(int i = 1; i < n; ++i) {
        int tmp = curr_max;
        curr_max = max(nums[i], max(nums[i] * curr_max, nums[i] * curr_min));
        curr_min = min(nums[i], min(nums[i] * tmp, nums[i] * curr_min));
        maxval = max(maxval , curr_max);
    }        
    return maxval;
}

213. House Robber II(Medium)

這題是198. House Robber的延伸。除了相鄰點不可以偷之外，還多了頭尾相接的條件。

解法和House Robber一樣，但是最後的node必須根據node-0有沒有偷來決定，所以使用兩個array來記錄。

一個array紀錄有偷node-0，一個array來記錄沒偷node-0。

初始化array就變的很重要，因為偷了node-0，所以rob0[1]就不能偷。





















int rob(vector<int>& nums) {
    auto n = nums.size();
    if(n == 1) return nums[0];
    if(n == 2) return max(nums[0], nums[1]);
    vector<int> rob0(n, 0);
    vector<int> rob1(n, 0);
    rob0[0] = nums[0];
    rob0[1] = rob0[0];  // important
    rob1[1] = nums[1];
        
    for(int i = 2; i < n; ++i) {
        if(i == n - 1) {
            rob0[i] = rob0[i - 1];
            rob1[i] = max(rob1[i - 2] + nums[i], rob1[i - 1]);
        } else {
            rob0[i] = max(rob0[i - 2] + nums[i], rob0[i - 1]);
            rob1[i] = max(rob1[i - 2] + nums[i], rob1[i - 1]);
        }
    }    
    return max(rob0[n - 1], rob1[n - 1]);
}

337. House Robber III(Medium)

給一個binary tree，規則一樣如果偷相鄰兩個node就會通報警察。求出在不通報警察的情況下，可以得到的最佳金額。

一開始我用house robber的想法去解，從root推到leaf會遇到沒辦法求出最佳報酬的問題。因為會有加入重複數字的問題。

最好的解髮是從leaf推展到root，這樣就不會有加入重複數字的問題。

關鍵在於"不打劫"這個節點，則子節點也不一定要打劫。





















class Solution {
    int rub = 0;
    int norub = 1;
public:
    int rob(TreeNode* root) {
        vector<int> rtn = dfs(root);
        return max(rtn[rub], rtn[norub]);
    }
    vector<int> dfs(TreeNode *root) {
        if(!root) return vector<int>(2, 0);
        vector<int> left = dfs(root->left);
        vector<int> right = dfs(root->right);
        vector<int> rtn(2, 0);
        // 打劫這個node，則兩個子節點就不能打劫。
        rtn[rub] = left[norub] + right[norub] + root->val;
        // 不打劫這個node，則可打劫子節點，也可以不打劫子節點
        // 因為是要最大的報酬，所以取最大值。
        rtn[norub] = max(left[norub], left[rub]) + max(right[norub], right[rub]); 
        return rtn;
    }
};

740. Delete and Earn(Medium)

題目是想從array中找出最大的points，但是每次取一個數num，就必須把前後的數砍掉(num - 1, num + 1)。

這個問題其實也是House Robber，因為相鄰的數字不能取。

解題的重點是使用了一個vector<int>(10001, 0)，因為題目跟我們說數字的值域從1到10000。

可以使用map但是相對的判斷和前後取值會麻煩很多。








int deleteAndEarn(vector<int>& nums) {
    vector<int> sums(10001, 0);
    for (int num : nums) sums[num] += num;
    for (int i = 2; i < 10001; ++i) {
        sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
    }
    return sums[10000];
}

因為數字分散，所以先使用map來統計每個數字有幾個。

traverse整個map，如果目前和前一個差1就只能選目前，或是前兩個。
























int deleteAndEarn(vector<int>& nums) {
    map<int, int> m;
    //統計每個數字出現的次數
    for(auto& n : nums)
        m[n]++;
    auto n = m.size();
    vector<int> dp(n);
    // 取第一個最小的數字
    auto it = m.begin();       
    dp[0] = it->first * it->second; it++;
    for(int i = 1; i < n; ++i, ++it) {
        int cur = it->first * it->second;
        // 如果和前一個數字差一
        if(it->first == (prev(it)->first + 1)) {
            // special case,只有兩個數字，就是看要取哪一個最大
            if(i == 1)  
                dp[i] = max(dp[i - 1], cur);
            else
                dp[i] = max(dp[i - 1], cur + dp[i - 2]);     
        } else
            dp[i] = dp[i - 1] + cur; // 和前面數字不是差一，所以可以拿
    }
    return dp.back();
}

5. Longest Palindromic Substring(Medium)

給你一個字串s，找出當中最長的回文子字串。

每個字母都是長度1的回文。

長度2的回文，兩個字母都一樣。

長度3以上的回文，去掉頭尾也是回文。

string longestPalindrome(string s) {
    auto n = s.length();
    if(n == 1) return  s;
    int len{1}, idx{0};
    // declare an array
    int dp[n][n];
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            dp[i][j] = 0;
        
    for(int right = 0; right < n; ++right) {
        dp[right][right] = 1;
        for(int left = 0; left < right; ++left) {
            if(s[left] != s[right]) continue;
            int ll = right - left + 1;
            // 長度3以上的回文，去掉頭尾也是回文。                           
            if(ll > 2 && dp[left + 1][right - 1])
                dp[left][right] = max(dp[left + 1][right - 1] + 2, dp[left][right]);
            // 如果長度只有2
            if(ll == 2)
                dp[left][right] = max(2, dp[left][right]);
            // 如果是回文，也長度(ll)比len還大，更新len和idx
            if(dp[left][right] && ll > len) {
                len = ll;
                idx = left;
            }
        }
    }
    return s.substr(idx, len);
}

2022/1/31

因為迴文是從string中選出left和right，所以一個迴文用兩個變數來表示，使用2D DP。



















string longestPalindrome(string s) {
    auto n = s.length();
    vector<vector<int>> dp(n, vector<int>(n));
    int idx{0}, maxlen{1}, right, left;
    for(right = 0; right < n; ++right) {
        // 只有一個char一定是回文
        dp[right][right] = 1;
        for(left = 0; left < right; ++left) {
            // 當左右都是一樣，且長度小於等於3或是left, right縮小一個也是回文
            dp[left][right] = (s[left] == s[right] && (right - left <= 2 || dp[left + 1][right - 1]));
            // 紀錄最長的情況
            if(dp[left][right] && right - left + 1 > maxlen) {
                maxlen = right - left + 1;
                idx = left;
            }
        }
    }    
    return s.substr(idx, maxlen);
}

2022/06/14
用一個vector<vector<int>> dp來記錄，從i到j的substring是不是palindrome。簡單不容易出錯的方法就是好方法。

























string longestPalindrome(string s) {
    int sz = s.size();
    if(sz == 1) return s;
    vector<vector<int>> dp(sz, vector<int>(sz));
    int maxlen = 1, idx = 0;
    // dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1])
    // 因為dp[i + 1][j - 1] 所以i由大到小，j由小到大
    for(int i = sz - 1; i >= 0; --i) {
        for(int j = i; j < sz; ++j) {
            if(i == j) dp[i][j] = 1;
            else if(i + 1 == j) {
                if(s[i] == s[j]) dp[i][j] = 1;
            } else {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
            }
            if(dp[i][j] && j - i + 1 > maxlen) {
                maxlen = j - i + 1;
                idx = i;
            }
        }
    }
    // time complexity  : O(N^2)
    // space complexity : O(N^2) 
    return s.substr(idx, maxlen);
}

91. Decode Ways(Medium)

A->1, B->2, C->3，以此類推到Z->26，可以編碼成一串數字。試問這串數字有幾種解碼方式。

自己可以解碼(s[i] != 0)，則解碼的方式和dp[i - 1]一樣。

自己可以和前面合併起來解碼(10~26)，則解碼的方式和dp[i - 2]一樣。

把這兩種相加就是從0~i的解碼方式dp[i]。















int numDecodings(string s) {
    auto n = s.length();
    if(n == 0 || s[0] == '0') return 0;
    vector<int> dp(n);
    dp[0] = 1;
    for(int i = 1; i < n; ++i) {
        // s[i]可以自己一個解碼，所以有dp[i - 1]種組合
        dp[i] += (s[i] == '0' ? 0 : dp[i - 1]);
        // s[i]可以和前面合併一起解碼，所以有dp[i - 2]種組合
        if(s[i - 1] == '1' || (s[i - 1] =='2' && s[i] <= '6'))
            dp[i] += (i>= 2 ? dp[i - 2] : 1);
    }
        
    return dp[n - 1];
}

1143. Longest Common Subsequence(Medium)

給你兩個字串text1和text2，求出兩個共同的subsequence最大值。
subsequence定義就是char出現的順序不變，但是在text中不用連續。

dp[i][j]的定義是text1[0-i]和text2[0-j]共同的subsequence的最大長度。

case 1 : 如果text1[i] == text2[j]，則dp[i][j] = dp[i - 1][j - 1] + 1;

case 2 : 如果text1[i] != text2[j]，則dp[i - 1][j]和dp[i][j - 1]選一個最大的。

因為都會存取i - 1或是j - 1，所以vector的大小給大一點(n + 1)。
















int longestCommonSubsequence(string text1, string text2) {
    auto n1 = text1.length();
    auto n2 = text2.length();
    vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
    int rtn{0};
    for(int i = 1; i < n1 + 1; ++i) {
        for(int j = 1; j < n2 + 1; ++j) {
            if(text1[i - 1] == text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            rtn = max(rtn, dp[i][j]);
        }
    }
    return rtn;
}

72. Edit Distance(Hard)

給你兩個字串word1和word2，一次可以replace, insert和delete一個字元，求最小的次數可以把word1變成word2。



















int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int i = 0; i <= n; ++i) dp[0][i] = i;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // 字元相同，則不用作任何操作。
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                //字元不同，則為了讓word1[0-i]等於word2[0-j]，
                //使用了 replace, delete,insert的最小值
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    return dp[m][n];
}

983. Minimum Cost For Tickets(Medium)

給你一個vector<int> days來表示一年中1~365哪一天會去旅行。另外vector<int> costs來表示1日卷，7日卷，和30日卷的價錢，求出旅行完days規定的天數後，最小的cost。

因為需要檢查days的天數，所以放入set可以快速檢視是否在days裡面。

這一天(day)的旅費是 day - 1使用1日卷，或是day-7使用7日卷，或是day-30使用30日卷的最小值。

如果這一天不旅行，則旅費和前一天一樣。
















int mincostTickets(vector<int>& days, vector<int>& costs) {
    // 放入set就不用一直檢查是否有重複的數字
    unordered_set<int> s(days.begin(), days.end());
    int lastday = days.back();
    vector<int> dp(lastday + 1);
    for(int i = 1; i <= lastday; ++i) {
        if(s.count(i)) {
            // 檢查買1日, 7日或是30日比較划算
            // 使用max(0, i - 7) 來避免取到負數               
            dp[i] = min(dp[max(0, i - 1)] + costs[0], 
                    min(dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2]));
        } else
            dp[i] = dp[i - 1];    // 和前一日一樣
    }
    return dp.back();
}

518. Coin Change 2

給你數個coins，求出可以排列成target的組合數目。











int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int coin : coins) {
        // 這邊從最前面找到最後面，因為可以重複使用coins中的數字
        for (int i = coin; i <= amount; ++i) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

另一種top-down的做法，每一個coins可以選擇要不要取。所以有兩個選項。




















class Solution {
    int helper(int amount, vector<int>& coins, int idx) {
        if(amount == 0) return 1;
        if(idx == -1) return 0;
        if(mem[amount][idx] > -1) return mem[amount][idx];
        int rtn;
        int nochange = helper(amount, coins, idx - 1);
        int dochange = 0;
        if(coins[idx] <= amount)
            dochange = helper(amount - coins[idx], coins, idx);
        return mem[amount][idx] = nochange + dochange;
    }
    vector<vector<int>> mem;
public:
    int change(int amount, vector<int>& coins) {
        int sz = coins.size();
        mem.resize(amount + 1, vector<int>(sz, -1));
        return helper(amount, coins, sz - 1);
    }
};

不可以重複使用的情況，請參考Target Sum

2218. Maximum Value of K Coins From Piles

給你k個piles，每個piles像一個stack一樣，只能依序從第一個開始拿，你只能拿k個coins，試問可以拿到的最大值。

因為最多可以拿k個，

所以對第一個piles來說有k+1個選項，不拿(0)，拿一個(1),…拿k個(k)。

當第一個piles拿了n個，則後面piles只能分配到k - n個。

所以helper的兩個input argument，第一個為目前在的piles，第二個為還剩下多少個k

和Coin change2類似，只是現在每一個有k+1個選項。























class Solution {
    int sz;
    vector<vector<int>> mem;
    int helper(vector<vector<int>>& piles, int from, int k) {
        if(from == sz || k == 0) return 0;
        if(mem[from][k] > 0) return mem[from][k];
        int res = helper(piles, from + 1, k); // 不取
        int cur = 0;
        //從piles from取1個,2個...N個
        for(int i = 0; i < min((int)piles[from].size(), k); ++i) {
            cur += piles[from][i];
            //改取下一個piles，且剩下k - i - 1 coins
            res = max(res, helper(piles, from + 1, k - i - 1) + cur);
        }
        return mem[from][k] = res;
    }
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        this->sz = piles.size();
        mem.resize(sz, vector<int>(k + 1));
        return helper(piles, 0, k);
    }
};

2023/04/15 daily challenge但是寫出了TLE的解答。

當初的想法是，每個piles有兩種可能，拿或是不拿

因為只用了拿和不拿，所以必須知道拿到第幾個。

所以先把piles反轉，從後面決定拿與不拿。

這樣其實條件比較複雜，因為每次會跟當下的piles相關。





















class Solution {
    int helper(vector<vector<int>>& piles, int k) {
        if(k == 0) return 0;
        int ans{0};
        for(auto& p : piles) {
            if(p.size() == 0) continue;
            int back = p.back();
            p.pop_back();
            int take = helper(piles, k - 1) + back;
            p.push_back(back);
            ans = max(ans, take);
        }
        return ans;
    }
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        for(auto& p : piles)
            reverse(p.begin(), p.end());
        return helper(piles, k);
    }
};

參考了lee215的解答。

其實想法和上面每個piles取與不取類似。

從一個piles[i]的角度來看所有的組合就是，取0個, 取1個到取min(piles[i].size(), k)

所以從上面所有的組合中再看helper(piles, idx + 1, rem - j - 1) 的所有組合。






















class Solution {
    int n;
    int helper(vector<vector<int>>& piles, int idx, int rem) {
        if(idx == n || rem == 0) return 0;
        if(mem[idx][rem]) return mem[idx][rem];
        // ans 從取0個開始
        int cur{0}, ans = helper(piles, idx + 1, rem);
        // 取1個，取2個，...，取min(piles[idx], rem)個
        for(int j = 0; j < rem && j < piles[idx].size(); ++j) {
            cur += piles[idx][j];
            ans = max(ans, helper(piles, idx + 1, rem - j - 1) + cur);
        }
        return mem[idx][rem] = ans;
    }
    vector<vector<int>> mem;
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        n = piles.size();
        mem.resize(n, vector<int>(k + 1));
        return helper(piles, 0, k);
    }
};

2420. Find All Good Indices

判斷是否為good indices。條件是在第i個的前k個是遞減數列，後k個是遞增數列。

只會使用brust force結果就TLE。

再來想到用2D DP(vector<vector<bool>>)來記錄開始和結束是遞增或是遞減，但是這樣做沒什麼效率。可能是想到判斷回文的關係。

使用1D DP來記錄到目前為止，遞增或是遞減的數列長度。

最後只要判斷i的前後是否大於等於k即可。

vector<int> goodIndices(vector<int>& nums, int k) {
    int sz = nums.size();
    vector<int> fwd(sz, 1), bwd(sz, 1);
    for(int i = 1, j = sz - 2; i < sz; ++i, --j)
        if(nums[i] <= nums[i - 1]) fwd[i] = fwd[i - 1] + 1;
        
    for(int i = sz - 2; i >= 0; --i)
        if(nums[i] <= nums[i + 1]) bwd[i] = bwd[i + 1] + 1;
        
    vector<int> ans;
    for(int i = k; i < sz - k; ++i) {
        if(fwd[i - 1] >= k && bwd[i + 1] >= k)
            ans.push_back(i);
    }
        
    return ans;
}

1031. Maximum Sum of Two Non-Overlapping Subarrays

因為fistLen和secondLen可以在任意位置，不好思考。

先假設firstLen一定在secondLen的前面。

則在 idx = i 的時候，後面subarray的firstLen最大值 + 前面subarray的secondLen的最大值和，

即為 idx = i 的時候的最好情況，所以我們要找出所有index的情況

在考慮 secondLen和firstLen的情況。

為什麼是dynamic programming? 因為dp1[i] = max(dp[i - 1], sum);每次都紀錄從i往前/往後看的最大值。







































class Solution {
public:
    int helper(vector<int>&nums,int x,int y){
        int n=nums.size();
        vector<int>dp1(n,0),dp2(n,0);
        int sum=0;
        for(int i=0;i<n;i++){
            if(i<x){//when we haven't considered x-size array
                sum+=nums[i]; 
                dp1[i]=sum;
            }
            else{ //when we have a window of size x
                sum=sum+nums[i]-nums[i-x];
                dp1[i]=max(dp1[i-1],sum);
            }
        }
        sum=0;
        
        for(int i=n-1;i>=0;i--){
            if(i+y>n-1) { //case when we haven't encountered a window of size secondlen ie. y
                sum+=nums[i];
                dp2[i]=sum;
            }
            else{//when we have a window of size secondLen
                sum=sum+nums[i]-nums[i+y];
                dp2[i]=max(dp2[i+1],sum);
            }
        }
        int ans=0;
        //our ans window will be from x-1 to n-y
        for(int i=x-1;i<n-y;i++){
            ans=max(ans,dp1[i]+dp2[i+1]);
        }
        return ans;
    }
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen){
        return max(helper(nums, firstLen, secondLen),helper(nums, secondLen, firstLen));
    }
};

2466. Count Ways To Build Good Strings

why dynamic programming?
因為string長度為len的字串，可以從string長度為len - zero或是len - one來推得。

建立string的條件就是在string後面增加某些zero或是某些one。

為什麼要走訪全部的lenght直到high?
因為長度為len的string是由更短的字串所建立而成，所以必須要從長度為1開始走訪。
從前一個狀態推展到目前狀態?
if(i - zero > 0) dp[i] += dp[i - zero];
if(i - one >= 0) dp[i] += dp[i - one];
起始狀態，dp[0] = 1，因為當長度跟one或是zero一樣的時候，就是使用這個來建立字串。









































class Solution {
    // dynamic programming 
    // 從上一個狀態，推展到這個狀態
    // 這個狀態就是長度i的string, 會得到這個長度的string有四種可能
    // 1. 從 i - zero長度的string, append zero
    // 2. 從 i - one 長度的string, append one
    // 3. zero自己本身是長度i
    // 4. one自己本身是長度i
    
    unordered_map<int, int> m; // len, count
    int mod = 1e9 + 7;
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        /*
        int ans = 0;
        for(int i = 1; i <= high; ++i) {
            if(m.count(i - zero)) m[i] = m[i - zero];
            if(m.count(i - one)) m[i] = (m[i] + m[i - one]) % mod;
            if(i == zero) m[i]++;
            if(i == one) m[i]++;
            //cout << i << "," << m[i] << endl;
            if(i >= low) ans = (ans + m[i]) % mod;
        }
        return ans;
        */
        vector<int> dp(high + 1); // len
        dp[0] = 1;
        int ans{0};
        for(int i = 1; i <= high; ++i) {
            if(i - zero >= 0) dp[i] = (dp[i] + dp[i - zero]) % mod;
            if(i - one >= 0) dp[i] = (dp[i] + dp[i - one]) % mod;
            if(i >= low) ans = (ans + dp[i]) % mod;
        }
        return ans;
    }
};
// low =  2, high = 3, zero = 1, one = 2
// len = 1, 2, 3
// len = 1 -> 0
// len = 2 -> 00, 11
// len = 3 -> 000, 110, 011

1130. Minimum Cost Tree From Leaf Values

一開始解不出來是因為題目沒弄懂。

left node是從array依序放入，重點是依序。

往上傳是left或是right的最大值。

因為需要同時知道sum和left/right的最大值，所以使用pair來當return值。





























class Solution {
    //sum, max(left, right)
    pair<int, int> helper(vector<int>& arr, int i, int j) {
        pair<int, int> rtn = {INT_MAX, INT_MAX};
        if(~mem[i][j].first) return mem[i][j];
        if(i == j) rtn = {0, arr[i]};
        else {
            for(int k = i; k < j; ++k) {
                auto l = helper(arr, i, k);
                auto r = helper(arr, k + 1, j);
                // sum即為兩邊做大值的product加上兩邊的和
                int sum = l.second * r.second + l.first + r.first;
                if(rtn.first > sum) {
                    rtn.first = sum;
                    // 題意是說left或是right的最大值
                    rtn.second = max(l.second, r.second); 
                }
            }
        }
        return mem[i][j] = rtn;
    }
    vector<vector<pair<int, int>>> mem;
public:
    int mctFromLeafValues(vector<int>& arr) {
        int sz = arr.size();
        mem.resize(sz, vector<pair<int, int>>(sz, make_pair(-1, -1)));
        return helper(arr, 0, sz - 1).first;
    }
};

1262. Greatest Sum Divisible by Three

給你一個vector<int>，返回最大的element sum，可以被3整除。

Greedy的解法是，全部加起來後，看餘數是多少減掉餘數最小的值。

參考lee215的答案，發現DP才是最漂亮的解法。

從第n個數值的角度來看，他可以和前面三種狀態(remain = 0, 1, 2)，組合出新的sum，並且更新vector<int> dp。









int maxSumDivThree(vector<int>& nums) {
    vector<int> dp(3);
    for(auto& n : nums) { // n和每個可能組合成一個新的
        for(auto& i : vector<int>(dp)) { // copy constructor 因為我們取用的資料不能被update
            dp[(i + n) % 3] = max(dp[(i + n) % 3], i + n);
        }
    }
    return dp[0];
}

1911. Maximum Alternating Subsequence Sum










































class Solution {
    vector<vector<long long>> mem;
    long helper(vector<int>& nums, int idx, int mul) {
        if(idx == nums.size()) return 0;
        int i = mul != -1;
        if(mem[idx][i] != LONG_MIN) return mem[idx][i];
        long long take = helper(nums, idx + 1, -mul) + nums[idx] * mul;
        long long notake = helper(nums, idx + 1, mul);
        return mem[idx][i] = max(take, notake);
        // mem[idx][0] = max(mem[idx + 1][1] + nums[idx], mem[idx + 1][0]);
        // mem[idx][1] = max(mem[idx + 1][0] - nums[idx], mem[idx + 1][1])
    }
public:
    long long maxAlternatingSum(vector<int>& nums) {
        /* top-down : memorization
        mem.resize(nums.size(), vector<long long>(2, LONG_MIN));
        return helper(nums, 0, 1);
        */

        // bottom-up : tabulation
        /*enum st{even, odd};
        vector<vector<long long>> dp(2, vector<long long>(nums.size() + 1));
        for(int i = nums.size() - 1; i >= 0; --i) {
            dp[even][i] = max(dp[even][i + 1], dp[odd][i + 1] + nums[i]);
            dp[odd][i] = max(dp[odd][i + 1], dp[even][i + 1] - nums[i]);
        }
        return max(dp[even][0], dp[odd][0]);
        // time complexity : O(N)
        // space complexity : O(N)
        */

        // reduce the space
        long long even{}, odd{};
        for(int i = nums.size() - 1; i >= 0; --i) {
            even = max(even, odd + nums[i]);
            odd = max(odd, even - nums[i]);
        }
        return max(even, odd);
        // time complexity : O(N)
        // space complexity : O(1)
    }
};

1751. Maximum Number of Events That Can Be Attended II

給你一個vector<vector<int>> events，其中有start, end和value, 選的events不能重疊，返回最大的value sum。

因為選這個event必須和上一個不重疊

一開始會用prev, current來表示，但是這樣就會多一個變數

如果確定要選current，那下一個可以直接跳到可以選擇的next，而不是一個一個跳，這樣就可以避免使用兩個變數。
































class Solution {
    int n;
    vector<vector<int>> dp;
    enum st{start, end, value};
    int helper(vector<vector<int>>& events, int cur, int k) {
        if(cur == n || k == 0) return 0;
        if(~dp[cur][k]) return dp[cur][k];
        int next; // 找出如果選擇cur的下一個可以選擇的event
        for(next = cur + 1; next < n; ++next)
            if(events[cur][end] < events[next][start]) break;
        return dp[cur][k] = 
               max(helper(events, cur + 1, k),
                   helper(events, next, k - 1) + events[cur][value]);
        // dp[cur][k] = max(dp[cur + 1][k], dp[next][k - 1] + events[cur][value]);
        //        cur
        //        /|\
        //  k   -->|   
    }
public:
    int maxValue(vector<vector<int>>& events, int k) {
        n = events.size();
        dp.resize(n, vector<int>(k + 1, -1));// O(N)
        sort(events.begin(), events.end()); // O(NlogN)
        // 因為使用memorizationation把n, k的組合都找一次
        // 所以是O(NK)，但是中間有找next的for loop
        // 所以是O(NK*N)
        // 如果找next改成binary search，則O(NKlogN)
        // time : O(N + NlogN + NKN) = O(N^2K)
        // space : O(NK) 
        return helper(events, 0, k);
    }
};

1444. Number of Ways of Cutting a Pizza

給你一個MxN的pizza，試問切成k等分，每個pizza都要有一個以上的蘋果，試問有多少種的切法。

先定義切法，不管垂直切或是水平切，切下去之後的上方或是左方給出去，剩下的再繼續切。

所以helper(y, x, k)，表示剩下的pizza從(y, x)開始到(m - 1, n - 1)。

使用apples來統計從(y, x)往下看剩下的apples方便以後的計算。

dynamic programming其實也是一種暴力破解，只是有記憶功能。








































class Solution {
    int m, n, mod;
    vector<vector<int>> apples;
    int helper(int y, int x, int k) {
        int& ans = mem[y][x][k];
        if(~ans) return ans;
        if(k == 1) return ans = apples[y][x] > 0;
        else {
            int ways{};
            //cut horizontal
            for(int i = y + 1; i < m; ++i) {
                if(apples[y][x] - apples[i][x] > 0)
                    ways = (ways + helper(i, x, k - 1)) % mod;
            }
            // cur vertical
            for(int i = x + 1; i < n; ++i) {
                if(apples[y][x] - apples[y][i] > 0)
                    ways = (ways + helper(y, i, k - 1)) % mod;
            }

            return ans = ways;
        }
    }
    vector<vector<vector<int>>> mem;
public:
    int ways(vector<string>& pizza, int k) {
        m = pizza.size();
        n = pizza[0].size();
        mod = 1e9 + 7;
        apples.resize(m + 1, vector<int>(n + 1));
        for(int y = m - 1; y >= 0; --y) // O(MN)
            for(int x = n - 1; x >= 0; --x)
                apples[y][x] = apples[y + 1][x] + apples[y][x + 1] - apples[y + 1][x + 1] 
                            + (pizza[y][x] == 'A');
        mem.resize(m, vector<vector<int>>(n, vector<int>(k + 1, -1)));    
        return helper(0, 0, k);
        // time : O(MNK)
        // space : O(MN + MNK)
    }
};

1048. Longest String Chain

找出最長的string chain，string chain的定義是，字串刪掉一個char會等於前一個字串。

因為string chain是字數少的在前面，所以對words針對size排序。

嘗試所有刪掉一個char的可能，來找出前一個string。

















int longestStrChain(vector<string>& words) {
    sort(begin(words), end(words), [](auto& str1, auto& str2){ // O(NlogN)
        return str1.size() < str2.size();
    });
    unordered_map<string, int> m;
    int ans{};
    for(auto& w : words) { // O(NM)
        for(int i = 0; i < w.size(); ++i) {
            string prev = w.substr(0, i) + w.substr(i + 1);
            m[w] = max(m[w], m[prev] + 1);
        }
        ans = max(ans, m[w]);
    }
    return ans;
    // time  : O(NM + NlogN) = O(NM)
    // space : O(logN + N) = O(N)
}

2646. Minimize the Total Price of Trips

給你一個undirected graph，每個node都有不同的price。給你一個vector<vector<int>> Trips，求所有路徑經過node的和為最小。在開始前可以把不相鄰的node價錢砍半。

統計每個node經過的次數。

不相鄰的node價錢砍半，和house robber一樣，
如果parent node價錢砍半，則child node價錢一定不能砍半。
如果parent node價錢沒砍半，則child node可以砍半，也可以不砍半。

使用dynamic programming來找出最小值。

為什麼memory vector不需要紀錄parent?
因為parent在之後的f()用不到。
















































class Solution {
    unordered_map<int, vector<int>> adj;
    vector<int> freq;
    vector<vector<int>> mem;
    bool dfs(int p, int s, int e) {
        if(s == e) return true;
        for(auto& nxt : adj[s]) {
            if(nxt == p) continue;
            freq[nxt]++;
            if(dfs(s, nxt, e)) return true;
            freq[nxt]--;
        }
        return false;
    }
    // 為什麼mem不需要紀錄parent?
    // helper(node, parent, parentHalved) = f(helper(nxt, node, 0), helper(nxt, node, 1))
    // f() 中不需要使用parent，parent是由node取代，nxt也是由node得到
    // 所以mem不須紀錄parent
    int helper(vector<int>& price, int node, int parent = -1, int parentHalved = 0) {
        if(~mem[node][parentHalved]) return mem[node][parentHalved];
        int res1 = freq[node] * price[node] / 2;
        int res2 = freq[node] * price[node];
        for(auto& nxt : adj[node]) {
            if(nxt == parent) continue;
            res2 += helper(price, nxt, node, 0);
        }
        if(parentHalved) return mem[node][parentHalved] = res2; // 如果parent價錢砍半，則目前的node不能砍半
        for(auto& nxt : adj[node]) {
            if(nxt == parent) continue;
            res1 += helper(price, nxt, node, 1);
        }
        return mem[node][parentHalved] = min(res1, res2); // 如果parent價錢沒砍半，則目前的node可以砍半，或是不用砍半
    }
public:
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        for(auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        freq.resize(n);
        for(auto& t : trips) {
            freq[t[0]]++;
            dfs(-1, t[0], t[1]);
        }
        mem.resize(n, vector<int>(2, -1));
        return helper(price, 0);
    }
};

1239. Maximum Length of A Concatenated String with Unique Characters

這題可以使用不同形式的DP來求解，重點是如何快速判斷string之間有unique char，使用bit manipulation。





























class Solution {
    vector<int> alpha, unique;
    int helper(int val, int idx) {
        if(idx == alpha.size()) return __builtin_popcount(val);
        else if(!unique[idx]) return helper(val, idx + 1);
        else {
            int notake = helper(val, idx + 1);
            int take{};
            if((val & alpha[idx]) == 0) take = helper(val | alpha[idx], idx + 1);
            return max(take, notake);
        }
    }
public:
    int maxLength(vector<string>& arr) {
        int sz = arr.size();
        alpha.resize(sz);
        unique.resize(sz, true);
        for(int i = 0; i < sz; ++i) {
            for(auto& c : arr[i]) {
                int shift = 1 << (c - 'a');
                if(alpha[i] & shift) // duplicate in this word
                    unique[i] = false; // never take this word
                alpha[i] |= 1 << (c - 'a');
            }
        }
        int val{}, idx{};
        return helper(val, idx);
    }
};

參考lee215的解答




















class Solution {
public:
    int maxLength(vector<string>& arr) {
        vector<bitset<26>> dp = {bitset<26>()}; // default : put one emoty bitset
        int res{};
        for(auto& s : arr) {
            bitset<26> a;
            for(auto& c : s)
                a.set(c - 'a');
            if(a.count() < s.size()) continue;
            for(int i = dp.size() - 1; i >= 0; --i) { // 從後面開始取就不會有重複問題
                bitset c = dp[i];
                if((c & a).any()) continue; // c 和 a有交集
                dp.push_back(c | a);
                res = max(res, (int)c.count() + (int)a.count());
            }
        }
        return res;
    }
};

1043. Partition Array for Maximum Sum
























class Solution {
    int sz, k;
    // 從idx往後看有那些可能?
    // subarray size = 1, 2, 3, ... k
    // 嘗試每一種可能的subarray。
    int helper(vector<int>& arr, int idx) {
        if(~mem[idx]) return mem[idx];
        int ans{}, maxv{};
        for(int i = idx; i < idx + k && i < arr.size(); ++i) {
            maxv = max(maxv, arr[i]);
            ans = max(ans, maxv * (i - idx + 1) + helper(arr, i + 1));
        }
        return mem[idx] = ans;
    }
    vector<int> mem;
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        sz = arr.size();
        this->k = k;
        mem.resize(sz + 1, -1);
        mem.back() = 0;
        return helper(arr, 0);
    }
};

1696. Jump Game VI

top down + memory -> TLE




















class Solution {
    int helper(vector<int>& nums, int k, int idx) {
        if(mem[idx] != INT_MIN) return mem[idx];
        int ans = INT_MIN;
        for(int nxt = idx + 1; nxt <= min(idx + k, (int)nums.size() - 1); ++nxt) {
            ans = max(ans, nums[idx] + helper(nums, k, nxt));
        }
        return mem[idx] = ans;
    }
    vector<int> mem;
public:
    int maxResult(vector<int>& nums, int k) {
        //因為答案有可為-1，所以改成INT_MIN
        mem.resize(nums.size(), INT_MIN); 
        mem.back() = nums.back();
        return helper(nums, k, 0);
    }
    // time : O(NK)
    // space : O(N)
};

改成bottom-up tabulation 也是TLE，因為time complexity一樣。














class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        vector<int> dp(nums.size(), INT_MIN);
        dp.back() = nums.back();
        for(int i = nums.size() - 2; i >= 0; --i) {
            for(int nxt = i + 1; nxt <= min(i + k, (int)nums.size() - 1); ++nxt)
                dp[i] = max(dp[i], nums[i] + dp[nxt]);
        }
        return dp.front();
        // time : O(NK)
        // space : O(N)
    }
}

因為是找後k個最大值，所以可以使用multiset，可以降低複雜度















class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        vector<int> dp(nums.size());
        multiset<int> ms{dp.back() = nums.back()};
        for(int i = nums.size() - 2; i >= 0; --i) {
            if(i + k + 1 < nums.size()) ms.erase(ms.find(dp[i + k + 1]));
            dp[i] = nums[i] + *ms.rbegin();
            ms.insert(dp[i]);
        }
        return dp.front();
        // time : O(NlogK)
        // space : O(N + K)
    }
};

因為是slind window maximum可以使用deque
















class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        vector<int> dp(nums.size());
        dp.back() = nums.back();
        deque<int> q{(int)nums.size() - 1};
        for(int i = nums.size() - 2; i >= 0; --i) { 
            while(!q.empty() && q.front() > i + k) q.pop_front();
            dp[i] = dp[q.front()] + nums[i];
            while(!q.empty() && dp[i] > dp[q.back()]) q.pop_back();
            q.push_back(i);
        }
        return dp.front();
        // time : O(N)
    }
};

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

Leetcode刷題學習筆記–Dynamic Programming

Introduction

Problems

tags: leetcode 刷題

tags: `leetcode` `刷題`