算法学习第十六天：动态规划（补充题目）

动态规划题

目录

1. 最大乘积子数组
2. 股票买卖问题
3. 最长递增子序列
4. 零钱兑换
5. 编辑距离

---

最大乘积子数组

问题描述

给定一个整数数组，求乘积最大的连续子数组的乘积。

关键点

• 需要同时记录当前最大值和最小值（负负得正）
• 状态转移方程：
  • max_dp[i] = max(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])
  • min_dp[i] = min(nums[i], max_dp[i-1]*nums[i], min_dp[i-1]*nums[i])

C++代码

int maxProduct(vector<int>& nums) {int max_val = nums[0], min_val = nums[0], res = nums[0];for (int i = 1; i < nums.size(); ++i) {int tmp_max = max({nums[i], max_val * nums[i], min_val * nums[i]});int tmp_min = min({nums[i], max_val * nums[i], min_val * nums[i]});max_val = tmp_max;min_val = tmp_min;res = max(res, max_val);}return res;
}

---

股票买卖问题

通用动态规划思路

• 状态定义：dp[i][k][0/1] 表示第i天，最多交易k次，是否持有股票时的最大利润。
• 状态转移：
  • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

交易一次（LeetCode 121）

int maxProfit(vector<int>& prices) {int buy = INT_MIN, sell = 0;for (int price : prices) {buy = max(buy, -price);sell = max(sell, buy + price);}return sell;
}

交易无限次（LeetCode 122）

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

交易两次（LeetCode 123）

int maxProfit(vector<int>& prices) {int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;for (int price : prices) {buy1 = max(buy1, -price);sell1 = max(sell1, buy1 + price);buy2 = max(buy2, sell1 - price);sell2 = max(sell2, buy2 + price);}return sell2;
}

---

最长递增子序列

动态规划（O(n²)）

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

贪心+二分（O(n log n)）

int lengthOfLIS(vector<int>& nums) {vector<int> lis;for (int num : nums) {auto it = lower_bound(lis.begin(), lis.end(), num);if (it == lis.end()) lis.push_back(num);else *it = num;}return lis.size();
}

---

零钱兑换

动态规划

• 状态定义：dp[i]表示凑出金额i所需的最少硬币数。
• 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)

int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; ++i)for (int coin : coins)if (coin <= i)dp[i] = min(dp[i], dp[i - coin] + 1);return dp[amount] > amount ? -1 : dp[amount];
}

---

编辑距离

动态规划

• 状态定义：dp[i][j]表示将word1前i个字符转换为word2前j个字符的最小操作数。
• 状态转移：
  • 若word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
  • 否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for (int i = 0; i <= m; ++i) dp[i][0] = i;for (int j = 0; j <= n; ++j) dp[0][j] = j;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];elsedp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});return dp[m][n];
}