LIS算法

最长上升子序列

leetcode.300.最长递增子序列

leetcode.354. 俄罗斯套娃信封问题

leetcode.334. 递增的三元子序列

leetcode.1691. 堆叠长方体的最大高度

动态规划

dp[i] 代表以i为尾的 最长递增子序列
转移方程
dp[i] = max(dp[i],dp[1…i-1]+1)

leetcode.300. 最长上升子序列

问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

动态规划

思路分析

dp[i] 代表以i为结尾的最长上升子序列

leetcode.面试题 08.13. 堆箱子

问题描述

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组[wi, di, hi]表示每个箱子。

动态规划

思路分析

先对数组进行排序
dp[i] 代表0-i，以i为尾的最大高度

最大矩形

问题描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

动态规划

思路分析

柱状图中最大的矩形

问题描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

暴力法

思路分析

以柱子i的高度为基准的最大矩形面积

时间复杂度O(nn) 超时

买卖股票的最佳时机 IV

问题描述

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

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

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

动态规划

思路分析

买卖股票的最佳时机 III

问题描述

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

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

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

动态规划

思路分析

全排列 II

问题描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

DFS

思路分析

全排列

问题描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

DFS

思路分析

CHAPTER 1

usaco

Problem Types 问题类型：

Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems  

Section 1.1

Introduction

Section 1.2