date: 2020/02/04

最优化问题:记录局部最优解,复用中间结果(有时需要记录所有见过的结果,有时只需要记录最近的几个结果),既可以自上而下分解至原子问题(通常是用递归),也可以自下而上构造出目标(递归或迭代);有的时候自上而下分解会比较合理,它可以直接绕过一些不需要的中间结果。


070爬楼梯(简单)

https://leetcode-cn.com/problems/climbing-stairs

为了到达第n阶,要么从第n-1阶走一步,要么从第n-2阶走两步,可得递推公式:

,初始状态

int climbStairs(int n) {
    int one_step = 1, two_step = 0;
    for(int i = 1; i <= n; i++){
        two_step += one_step;
        swap(one_step, two_step);
    }
    return one_step;
}


120三角形最小路径和(中等)

https://leetcode-cn.com/problems/triangle

,初始状态

// 原位操作
int minimumTotal(vector<vector<int>>& triangle) {
    if(triangle.size() == 1) return triangle[0][0];
    for(int i = 1; i < triangle.size(); i++){
        triangle[i][0] += triangle[i-1][0];
        for(int j = 1; j < triangle[i].size() - 1; j++)
            triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j]);
        triangle[i][triangle[i].size()-1] += triangle[i-1][triangle[i].size()-2];
    }
    vector<int>& bottle_row = triangle[triangle.size()-1];
    return *min_element(bottle_row.begin(), bottle_row.end());
}


152乘积最大子序列(中等)

https://leetcode-cn.com/problems/maximum-product-subarray

转化为子问题:

已知序列

分别找到子序列的最大乘积后缀子序列(这里只表示乘积值)

显然,即为原始序列的最大子序列(乘积值)

针对子问题,有直觉上会有一些简单的联系。

具体来说,(初始状态:

也就是

依旧有

或者简单写成

此时显然除了最大乘积后缀,还得记录最小乘积后缀,

与最大值相反【等号放上面跟下面都一样】

int maxProduct(vector<int>& nums) {
    int maxp = 1, minp = 1, result = INT_MIN;
    for(int i = 0; i < nums.size(); i++){
        if(nums[i] < 0) swap(maxp, minp);
        maxp = max(nums[i], maxp * nums[i]);
        minp = min(nums[i], minp * nums[i]);
        if(maxp > result) result = maxp;
    }
    return result;
}


021买卖股票的最佳时机(简单)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

只做一次买卖。

一次遍历,记录见过的最低价,假设在最低买入在当前卖出,找到最大收益:空间O(1)时间O(n)


122买卖股票的最佳时机II(简单)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

多次买卖。

如果第i天价格比第i-1天价格高,那么就把这一天的收入纳进总收益

int maxProfit(vector<int>& prices) {
    int total_profit = 0;
    for(int i = 1; i < prices.size(); i++){
        int profit = prices[i] - prices[i-1];
        if(profit > 0)
            total_profit += profit;
    }
    return total_profit;
}

分别用表示第i天完成操作之后持有现金和持有股票的最大累积收益。

可得递推式,

,初始状态,最终收益为

到了最后一天,还继续持有股票肯定是不划算的,显然有,故最后答案可以简化为

int maxProfit(vector<int>& prices) {
    if(prices.size() <= 1)
        return 0;
    int hold_cash = 0, hold_stock = -prices[0];
    for(int i = 1; i < prices.size(); i++){
        int cash = hold_cash, stock = hold_stock;
        hold_cash = max(cash, stock + prices[i]);
        hold_stock = max(stock, cash - prices[i]);
    }
    return hold_cash;
}


123买卖股票的最佳时机III(困难)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

最多两次买卖。

与II相比,次数有{0, 1, 2}三种,持有情况有{现金, 股票}两种,组合起来共有种状态;

分别用表示第i天完成操作之后,且已完成j次买卖时,持有现金和持有股票的最大累积收益。

递推公式转化为

,初始状态

最终收益为

结算时持有股票必定是不划算的,显然有

允许买卖的次数越多,可操作的空间越多,显然有

综上,最后答案可以简化为

int maxProfit(vector<int>& prices) {
    if(prices.size() <= 1)
        return 0;
    vector<int> hold_cash(3, 0), hold_stock(3, -prices[0]);
    for(int i = 1; i < prices.size(); i++){
        vector<int> cash = hold_cash, stock = hold_stock;
        for(int j = 1; j < 3; j++)
            hold_cash[j] = max(hold_cash[j], hold_stock[j-1] + prices[i]);
        for(int j = 0; j < 3; j++)
            hold_stock[j] = max(hold_stock[j], hold_cash[j] - prices[i]);
    }
    return hold_cash[2];
}


188买卖股票的最佳时机IV(困难)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv

最多k次买卖。

上一题的进一步泛化情况,大体上把 3 换成 k+1 就能满足题目要求。但这里挖了个坑,k值不一定是合理的,万一给了个很大的k值,那么容易出现爆栈的情况。当时,显然退化程问题II 的无限次买卖问题。

int maxProfit(int k, vector<int>& prices) {
    if(prices.size() <= 1)
        return 0;
    
    if(k < prices.size() / 2){  // 问题III的扩展泛化
        vector<int> hold_cash(k + 1, 0), hold_stock(k + 1, -prices[0]);
        for(int i = 1; i < prices.size(); i++){
            vector<int> cash = hold_cash, stock = hold_stock;
            for(int j = 1; j < k + 1; j++)
                hold_cash[j] = max(hold_cash[j], hold_stock[j-1] + prices[i]);
            for(int j = 0; j < k + 1; j++)
                hold_stock[j] = max(hold_stock[j], hold_cash[j] - prices[i]);
        }
        return hold_cash[k];
    }else{   // 退化为问题II
        int hold_cash = 0, hold_stock = -prices[0];
        for(int i = 1; i < prices.size(); i++){
            int cash = hold_cash, stock = hold_stock;
            hold_cash = max(cash, stock + prices[i]);
            hold_stock = max(stock, cash - prices[i]);
        }
        return hold_cash;
    }
}


309最佳买卖股票时机含冷冻期(中等)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

多次买卖,一天冷冻期。

相比问题II ,在卖出股票后增加一个冷冻状态,递推公式变为

,初始状态,最终收益为

如果冷冻期不止一天,那么无非多了几个状态,多几回的冷冻期状态转移。

int maxProfit(vector<int>& prices) {
    if(prices.size() <= 1)
        return 0;
    int hold_cash = 0, hold_stock = -prices[0], cooldown = 0;
    for(int i = 1; i < prices.size(); i++){
        int cash = hold_cash, stock = hold_stock, cool = cooldown;
        hold_cash = max(cash, stock + prices[i]);
        hold_stock = max(stock, cool - prices[i]);
        cooldown = cash;
    }
    return max(hold_cash, cooldown);
}


714买卖股票的最佳时机含手续费(中等)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee

多次买卖,卖出需要手续费。

相比问题II ,只是在卖出卖出股票的时候额外减去一个固定手续费,递推公式为

,初始状态,最终收益为

int maxProfit(vector<int>& prices, int fee) {
    if(prices.size() <= 1)
        return 0;
    int hold_cash = 0, hold_stock = -prices[0];
    for(int i = 1; i < prices.size(); i++){
        int cash = hold_cash, stock = hold_stock;
        hold_cash = max(cash, stock + prices[i] - fee);
        hold_stock = max(stock, cash - prices[i]);
    }
    return hold_cash;
}


300最长上升子序列(中等)

https://leetcode-cn.com/problems/longest-increasing-subsequence

为待输入序列子序列包含的最长子序列的长度,

如果已知,为了得到包含的最长上升子序列,我们需要在中找到一个最长上升子序列(记它的最大长度为,而且加入之后依旧是上升序列——显然有

则有递推式

,其中令最终答案为

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size());
    int max_length = 0;
    for(int i = 0; i < nums.size(); i++){
        int max_dp = 0;
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j] && dp[j] > max_dp)
                max_dp = dp[j];
        }
        dp[i] = max_dp + 1;
        if(dp[i] > max_length) 
            max_length = dp[i];
    }
    return max_length;
}


322零钱兑换(中等)

https://leetcode-cn.com/problems/coin-change

按照常识,直觉上肯定是大面值的硬币越多,总的硬币越少。但这是建立在所用面值的硬币可以组合出任意数值的前提下,这道题指定了可以使用的面值,这样的直觉是行不通的。

在限定的硬币面值下,记录不同金额的最小硬币数

按需规划,,如果已经判断过,那么就可以直接复用中间结果,否则进一步分解

递推式:,其中

// 对于counter,用0表示未知,-1表示不存在
int helper(vector<int>& coins, int amount, vector<int>& counter){
    if(amount < 0) return -1;
    if(amount == 0) return 0;
    if(counter[amount-1] != 0) return counter[amount-1];

    int min_coin = INT_MAX;
    for(int i = 0; i < coins.size(); i++){
        int c = helper(coins, amount - coins[i], counter);
        if(c != -1 && c < min_coin)
            min_coin = c + 1;
    }
    counter[amount-1] = min_coin == INT_MAX ? -1 : min_coin;
    return counter[amount-1];
}

int coinChange(vector<int>& coins, int amount){
    vector<int> counter(amount, 0);
    return helper(coins, amount, counter);
}

依旧记录不同金额的最小硬币数

递推式:,其中,而初始状态

int coinChange(vector<int>& coins, int amount){
    vector<int> dp(amount + 1, INT_MAX - 1);  // 留点余量,后边好+1
    dp[0] = 0;
    for(int i = 1; i <= amount; i++){
        for(int j = 0; j < coins.size(); j++)
            if(i >= coins[j])
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
    }
    return dp[amount] == INT_MAX - 1 ? -1 : dp[amount];
}


072编辑距离(困难)

https://leetcode-cn.com/problems/edit-distance

已知字符串和字符串a[:i] b[:j] 的编辑距离记为

举个例子, a="horse", b="rose" ,考虑 i=3, j=2 ,此时 a[:i]="hor", b[:j]="ro" 

为了得到 "hor" 和 "ro" 的编辑距离,按照题目,有以下三种编辑方式:

    1. "hor"-(delete)->"ho"-->"ro" :
    2. "hor"-->"r"-(insert)->"ro" :
    3. "ho"+"r"-->"r"+"r"-(replace)->"r"+"o" :
      这里存在一种特殊情况,如果有,显然都不需要替换操作,直接有

综上,有递推式,初始状态

int minDistance(string word1, string word2) {
    vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1));
    for(int i = 0; i <= word1.size(); i++)
        dp[i][0] = i;
    for(int j = 0; j <= word2.size(); j++)
        dp[0][j] = j;

    for(int i = 1; i <= word1.size(); i++){
        for(int j = 1; j <= word2.size(); j++){
            if(word1[i-1] == word2[j-1])
                dp[i][j] = 1 + min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] - 1);
            else
                dp[i][j] = 1 + min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
        }
    }
    return dp[word1.size()][word2.size()];
}


牛客:01背包问题(knapsack)

https://www.nowcoder.com/questionTerminal/708f0442863a46279cce582c4f508658

动态规划:空间O(Vn)或O(V),时间O(Vn)

为前件物品在背包容量为的情况下的最大价值,分别是第件物品的体积和价值;
那么有递推式,初始状态

注意:如果只用一维数组滚动处理,必须从后往前更新,因为且每次计算时依赖于

#include <iostream>
#include <vector>

using namespace std;

int main(){
    // 获取 背包体积V 和 物品数量n
    int V, n;
    cin >> V >> n;
    // 获取每件物品的 体积w[i] 和 价值v[i]
    int w[n], v[n];
    for(int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    
    /* 动态规划1:空间复杂度O(Vn)
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= V; j++){
            if(j < w[i])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
        }
    }
    cout << dp[n][V] << endl;
    */
    // 动态规划2:空间复杂度O(V)
    vector<int> dp(V + 1, 0);
    for(int i = 0; i < n; i++){
        for(int j = V; j >= w[i]; j--){   // !!必须从后往前更新
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}


旅行商问题

比较难的一道动态规划


568最大休假天数(困难)

https://leetcode-cn.com/problems/maximum-vacation-days/

收费题,题目和题解可以参考以下截图:

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-568


字节2019春招 毕业旅行问题

https://www.nowcoder.com/test/16516564/summary

第五题

此处为语雀文档,点击链接查看:https://www.yuque.com/kjle6/akya3v/rk1ii4