https://leetcode-cn.com/tag/dynamic-programming/
题目汇总
264. 丑数 II中等
279. 完全平方数中等[✔]
300. 最长上升子序列中等[✔]
303. 区域和检索 - 数组不可变简单
304. 二维区域和检索 - 矩阵不可变中等（？？）
309. 最佳买卖股票时机含冷冻期中等
312. 戳气球困难
321. 拼接最大数困难（没做）
264. 丑数 II中等
编写一个程序，找出第
n个丑数。丑数就是质因数只包含2, 3, 5的正整数。
示例:
输入: n = 10
输出: 12
解释:1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前 10 个丑数。
**说明: **
1是丑数。n不超过1690。
思路：三指针+动态规划
利用三个指针，每次找到三组中最小的元素，然后指针后移
//2020.06.11
class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了84.88%的用户
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1; //丑数序列， 第 1 个丑数是 1
int p_2 = 0;
int p_3 = 0;
int p_5 = 0;
for (int i = 1; i < n; ++i)
{
dp[i] = Math.min(Math.min(2 * dp[p_2], 3 * dp[p_3]), 5 * dp[p_5]);
if(dp[i] == 2 * dp[p_2])
++p_2;
if(dp[i] == 3 * dp[p_3])
++p_3;
if(dp[i] == 5 * dp[p_5])
++p_5;
}
return dp[n - 1];//找出第 n 个丑数
}
}
279. 完全平方数中等
给定正整数 n，找到若干个完全平方数（比如
1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
示例 :
输入: n =13
输出: 2
解释:13 = 4 + 9.
思路：动态规划
时间复杂度：O(n*sqrt(n))，一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 sqrt(n)次迭代
class Solution {
public int numSquares(int n) {//执行用时 :66 ms, 在所有 Java 提交中击败了29.22%的用户
int[] dp = new int[n+1];
for(int i=1;i<=n;i++){
dp[i] = i;//最坏结果
for(int j=1;i-j*j>=0;j++){
dp[i] = Math.min(dp[i], dp[i - j * j] + 1); //动态转移方程
}
}
return dp[n];
}
}
300. 最长上升子序列中等
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4
解释: 最长的上升子序列是[2,3,7,101]，它的长度是4。
说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路一：动态规划，时间复杂度 O(n2)
class Solution {
public int lengthOfLIS(int[] nums) {//执行用时 :24 ms, 在所有 Java 提交中击败了13.95%的用户
if(nums.length <= 1)
return nums.length;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);//填充dp数组中的每个元素都是1
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i], dp[j] + 1);//dp[i]表示以nums[i]结尾的上升子序列的长度
}
}
}
int res = 0;
for(int i=0;i<dp.length;i++){
res = Math.max(res, dp[i]);// dp[i] 的最大值是最后要输出的值
}
return res;
}
}
思路二：二分查找，时间复杂度 O(nlogn)
根本想不到这道题和二分查找有关，扑克牌游戏可以很好解释二分查找解法，代码来自labuladong的算法小抄
class Solution {
public int lengthOfLIS(int[] nums) {//执行用时 :1 ms, 在所有 Java 提交中击败了92.79%的用户
int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要处理的扑克牌
int poker = nums[i];
/***** 搜索左侧边界的⼆分查找 *****/
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
// 没找到合适的牌堆，新建⼀堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS ⻓度
return piles;
}
}
303. 区域和检索 - 数组不可变简单
给定一个整数数组
nums，求出数组从索引i到j(i ≤ j) 范围内元素的总和，包含i, j两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
- 你可以假设数组不可变。
- 会多次调用 sumRange 方法。
思路：动态规划
//2020.06.10
class NumArray {//执行用时 :10 ms, 在所有 Java 提交中击败了99.07%的用户
private int[] sum;
public NumArray(int[] nums) {
//sum[i]存储nums中前i个元素的和，实际是nums[0....i-1]的和
sum = new int[nums.length + 1];
sum[0] = 0;
for (int i = 1; i < sum.length; i++) {
//前i个元素和 = 前i-1个元素和 + 第i个元素
sum[i] = sum[i - 1] + nums[i - 1];
}
}
public int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
304. 二维区域和检索 - 矩阵不可变中等
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
示例:
给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
说明:
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法。
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
思路：动态规划
class NumMatrix {//执行用时 :20 ms, 在所有 Java 提交中击败了38.00%的用户
private int[][] dp;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
dp = new int[matrix.length][matrix[0].length + 1];
for (int r = 0; r < matrix.length; r++) {
for (int c = 0; c < matrix[0].length; c++) {
dp[r][c + 1] = dp[r][c] + matrix[r][c];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int row = row1; row <= row2; row++) {
sum += dp[row][col2 + 1] - dp[row][col1];
}
return sum;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
309. 最佳买卖股票时机含冷冻期中等
相关题目：
121. 买卖股票的最佳时机简单
122. 买卖股票的最佳时机 II简单
123. 买卖股票的最佳时机 III困难
188. 买卖股票的最佳时机 IV困难
309. 最佳买卖股票时机含冷冻期中等
714. 买卖股票的最佳时机含手续费中等
给定一个整数数组，其中第* i* 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例: 输入: [1,2,3,0,2]，输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路：动态规划
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了99.20%的用户
public int maxProfit(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
int dp_pre_0 = 0; // 代表 dp[i-2][0]
for (int i = 0; i < n; i++) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
}
312. 戳气球困难
有
n个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中。
现在要求你戳破所有的气球。每当你戳破一个气球i时，你可以获得nums[left] * nums[i] * nums[right]个硬币。 这里的left和right代表和i相邻的两个气球的序号。注意当你戳破了气球i后，气球left和气球right就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤n≤ 500, 0 ≤nums[i]≤ 100
示例:
输入:[3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 167
思路：动态规划
重点在开区间巧妙的设计，自己没做出来，看了下边的题解很清晰，照此思路复现代码，必须给大佬个赞，太牛了！
https://leetcode-cn.com/problems/burst-balloons/solution/dong-tai-gui-hua-tao-lu-jie-jue-chuo-qi-qiu-wen-ti/
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
//添加两侧的虚拟气球，目的是让子问题独立
int[] newNums = new int[n + 2];
newNums[0] = 1;
newNums[n + 1] = 1;
for(int i=0;i<n;i++){
newNums[i+1] = nums[i];
}
int[][] dp = new int[n+2][n+2];
//i 应该从下往上
for(int i=n;i>=0;i--){
//j 应该从左往右
for(int j=i+1;j<n+2;j++){
//最后戳破的气球是 k
for(int k=i+1;k<j;k++){
dp[i][j] = Math.max(dp[i][j],dp[i][k]+dp[k][j]+newNums[i]*newNums[k]*newNums[j]);
}
}
}
return dp[0][n+1];
}
}
321. 拼接最大数困难
给定长度分别为
m和n的两个数组，其元素由0-9构成，表示两个自然数各位上的数字。现在从这两个数组中选出k (k <= m + n)个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入:nums1 =[3, 4, 6, 5]，nums2 =[9, 1, 2, 5, 8, 3]，k =5
输出:[9, 8, 6, 5, 3]
示例 2:
输入:nums1 =[6, 7]，nums2 =[6, 0, 4]，k =5
输出:[6, 7, 6, 0, 4]
示例 3:
输入:nums1 =[3, 9]，nums2 =[8, 9]，k =3
输出:[9, 8, 9]
网友评论