LeetCode题解——动态规划(五)

一时失言乱红尘 2023-07-21 11:24 20阅读 0赞

# 更多学习笔记[Github][] #

### 文章目录 ###

*  更多学习笔记\[Github\](https://wardseptember.github.io/notes/\#/)
 *  股票交易类型
 *   *  309. 最佳买卖股票时机含冷冻期
     *   *  动态规划
     *  714. 买卖股票的最佳时机含手续费
     *   *  动态规划
     *  123. 买卖股票的最佳时机 III
     *   *  动态规划
     *  188. 买卖股票的最佳时机 IV
     *   *  动态规划
 *  字符串编辑
 *   *  583. 两个字符串的删除操作
     *   *  动态规划
     *  72. 编辑距离
     *   *  动态规划
     *  650. 只有两个键的键盘
     *   *  递归
         *  动态规划
         *   *  推荐阅读

# 股票交易类型 #

## 309. 最佳买卖股票时机含冷冻期 ##

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。  
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。  
示例:

输入: \[1,2,3,0,2\]  
输出: 3  
解释: 对应的交易状态为: \[买入, 卖出, 冷冻期, 买入, 卖出\]

### 动态规划 ###

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            int[] dp = new int[3]; // dp[0]表示第i-2天没有持有股票，dp[1]表示第i天持有股票，dp[2]表示第i天不持有股票
            dp[1] = Integer.MIN_VALUE;
            int n = prices.length;
            for (int i = 0; i < n; ++i) {
        
                int temp = dp[2]; // 记录下第i天没有持有股票，手里的收益。
                dp[2] = Math.max(dp[2], dp[1] + prices[i]);
                dp[1] = Math.max(dp[1], dp[0] - prices[i]);
                dp[0] = temp;
            }
            return dp[2];
        }
    }

## 714. 买卖股票的最佳时机含手续费 ##

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

示例 1:

输入: prices = \[1, 3, 2, 8, 4, 9\], fee = 2  
输出: 8  
解释: 能够达到的最大利润:  
在此处买入 prices\[0\] = 1  
在此处卖出 prices\[3\] = 8  
在此处买入 prices\[4\] = 4  
在此处卖出 prices\[5\] = 9  
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.  
注意:

0 < prices.length <= 50000.  
0 < prices\[i\] < 50000.  
0 <= fee < 50000.

### 动态规划 ###

class Solution {
        
        public int maxProfit(int[] prices, int fee) {
        
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            int[] dp = new int[3]; // dp[0]表示第i天没有持有股票，dp[1]表示第i天持有股票
            dp[1] = Integer.MIN_VALUE;
            int n = prices.length;
            for (int i = 0; i < n; ++i) {
        
                int temp = dp[0]; // 记录下第i-1天没有持有股票，手里的收益。
                dp[0] = Math.max(dp[0], dp[1] + prices[i]); // 计算第i天没有持有股票，手里的收益。
                dp[1] = Math.max(dp[1], temp - prices[i] - fee); // 计算第i天持有股票，手里的收益,每次买入减去手续费即可。
            }
            return dp[0];
        }
    }

## 123. 买卖股票的最佳时机 III ##

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: \[3,3,5,0,0,3,1,4\]  
输出: 6  
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。  
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。  
示例 2:

输入: \[1,2,3,4,5\]  
输出: 4  
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。  
示例 3:

输入: \[7,6,4,3,1\]  
输出: 0  
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

### 动态规划 ###

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            int firstBuy = Integer.MIN_VALUE, firstSell = 0;
            int secondBuy = Integer.MIN_VALUE, secondSell = 0;
            for (int price : prices) {
        
                if (firstBuy < -price) {
         // 入手最便宜的股票
                    firstBuy = -price; //花了多少钱
                }
                if (firstSell < firstBuy + price) {
         // 第一次交易收益最大化
                    firstSell = firstBuy + price;
                }
                if (secondBuy < firstSell - price) {
         // 第二次入手最便宜股票
                    secondBuy = firstSell - price;
                }
                if (secondSell < secondBuy + price) {
        
                    secondSell = secondBuy + price;
                }
            }
            return secondSell;
        }
    }

## 188. 买卖股票的最佳时机 IV ##

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: \[2,4,1\], k = 2  
输出: 2  
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。  
示例 2:

输入: \[3,2,6,5,0,3\], k = 2  
输出: 7  
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。  
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

### 动态规划 ###

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            int n = prices.length;
            if (k >= n / 2) {
        
                int maxProfit = 0;
                for (int i = 1; i < n; i++) {
        
                    if (prices[i] > prices[i - 1]) {
        
                        maxProfit += prices[i] - prices[i - 1];
                    }
                }
                return maxProfit;
            }
            int[][] maxProfit = new int[k + 1][n];
            for (int i = 1; i <= k; ++i) {
        
                int localMax = maxProfit[i - 1][0] - prices[0];
                for (int j = 1; j < n; ++j) {
        
                    maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
                    localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
                }
            }
            return maxProfit[k][n - 1];
        }
    }

# 字符串编辑 #

## 583. 两个字符串的删除操作 ##

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入: “sea”, “eat”  
输出: 2  
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

给定单词的长度不超过500。  
给定单词中的字符只含有小写字母。

### 动态规划 ###

class Solution {
        
        public int minDistance(String word1, String word2) {
        
            int m = word1.length(), n = word2.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
        
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return m + n - 2 * dp[m][n];
        }
    }

## 72. 编辑距离 ##

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符  
删除一个字符  
替换一个字符  
示例 1:

输入: word1 = “horse”, word2 = “ros”  
输出: 3  
解释:  
horse -> rorse (将 ‘h’ 替换为 ‘r’)  
rorse -> rose (删除 ‘r’)  
rose -> ros (删除 ‘e’)  
示例 2:

输入: word1 = “intention”, word2 = “execution”  
输出: 5  
解释:  
intention -> inention (删除 ‘t’)  
inention -> enention (将 ‘i’ 替换为 ‘e’)  
enention -> exention (将 ‘n’ 替换为 ‘x’)  
exention -> exection (将 ‘n’ 替换为 ‘c’)  
exection -> execution (插入 ‘u’)

### 动态规划 ###

class Solution {
        
        public int minDistance(String word1, String word2) {
        
            if (word1 == null || word2 == null) {
        
                return 0;
            }
            int m = word1.length(), n = word2.length();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
        
                dp[i][0] = i;
            }
            for (int i = 1; i <= n; ++i) {
        
                dp[0][i] = i;
            }
            for (int i = 1; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
        
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    }
                }
            }
            return dp[m][n];
        }
    }

## 650. 只有两个键的键盘 ##

最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。  
Paste (粘贴) : 你可以粘贴你上一次复制的字符。  
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。

示例 1:

输入: 3  
输出: 3  
解释:  
最初, 我们只有一个字符 ‘A’。  
第 1 步, 我们使用 Copy All 操作。  
第 2 步, 我们使用 Paste 操作来获得 ‘AA’。  
第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。  
说明:

n 的取值范围是 \[1, 1000\] 。

### 递归 ###

class Solution {
        
        public int minSteps(int n) {
        
            if (n == 1) {
        
                return 0;
            }
            int h = (int) Math.sqrt(n);
            for (int i = 2; i <= h; ++i) {
        
                if (n % i == 0) {
        
                    return i + minSteps(n / i);
                }
            }
            return n;
        }
    }

### 动态规划 ###

class Solution {
        
        public int minSteps(int n) {
        
            int[] dp = new int[n + 1];
            int h = (int) Math.sqrt(n);
            for (int i = 2; i <= n; ++i) {
        
                dp[i] = i;
                for (int j = 2; j <= h; ++j) {
        
                    if (i % j == 0) {
        
                        dp[i] = dp[j] + dp[i / j];
                        break;
                    }
                }
            }
            return dp[n];
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Github]: https://wardseptember.github.io/notes/#/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20230528/77c3422ba46c45d0a8b24835a3a41678.png