①动态规划
动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果
⓿动规五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
❶基础规划题
509. 斐波那契数
斐波那契数 (通常用 F(n)
表示)形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n
,请计算 F(n)
。
示例 1:
输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3
//动态规划
class Solution {
public int fib(int n) {
if (n < 2) return n;
int dp[] = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
//优化
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
//递归
class Solution {
public int fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
本问题其实常规解法可以分成多个子问题,爬第n阶楼梯的方法数量,等于 2 部分之和
- 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
- 爬上 n−2 阶楼梯的方法数量,因为再爬2阶就能到第n阶
所以我们得到公式 dp[n] = dp[n−1] + dp[n−2],同时需要初始化 dp[0]=1 和 dp[1]=1
时间复杂度:O(n)
class Solution {
public int climbStairs(int n) {
int dp[] = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
746. 使用最小花费爬楼梯
给你一个整数数组 cost
,其中 cost[i]
是从楼梯第 i
个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0
或下标为 1
的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1:
输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
示例 2:
输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。
- 确定dp数组以及下标的含义
- dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]
- 确定递推公式
- 有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]
- dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
- dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
- 那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?
- 一定是选最小的,所以
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
;
- dp数组如何初始化
题目描述中明确说了 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。” 也就是说到达第 0 、1个台阶是不花费的,但从 第0 个台阶往上跳的话,需要花费 cost[0]。所以初始化 dp[0] = 0,dp[1] = 0;
- 确定遍历顺序
因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int dp[] = new int[n + 1];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= n; i++){
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
118. 杨辉三角
给定一个非负整数 numRows
,生成「杨辉三角」的前 numRows
行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < numRows; i++){
List<Integer> row = new ArrayList<Integer>();
for (int j = 0; j <= i; j++) {
if(j == 0 || j == i) row.add(1);
else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
res.add(row);
}
return res;
}
}
62. 不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3
输出:28
示例 4:
输入:m = 3, n = 3
输出:6
我们令 dp[i][j]
是到达 i, j
最多路径
动态方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]
注意,对于第一行 dp[0][j]
,或者第一列 dp[i][0]
,由于都是在边界,所以只能为 1
class Solution {
public int uniquePaths(int m, int n) {
int dp[][] = new int[m][n];
//初始化
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
//到达i行j列的路径条数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
63. 不同路径 II
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int dp[][] = new int[m][n];
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
dp[i][0] = 1;
}
for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++){
dp[0][j] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 0){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
343. 整数拆分
剑指 Offer 14- I. 剪绳子 - 力扣(Leetcode)
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
动规五部曲,分析如下:
- 确定dp数组以及下标的含义
dp[i]
:分拆数字 i
,可以得到的最大乘积为dp[i]
。
- 确定递推公式
当 i ≥ 2
时,假设对正整数 i
拆分出的第一个正整数是 j
(1 ≤ j < i
),则有以下两种方案:
- 将
i
拆分成j
和i−j
的和,且i−j
不再拆分成多个正整数,此时的乘积是j×(i−j)
; - 将
i
拆分成j
和i−j
的和,且i−j
继续拆分成多个正整数,此时的乘积是j×dp[i−j]
。
递推公式:dp[i]=max{dp[i], j×(i−j), j×dp[i−j]}
- dp的初始化
初始化 dp[2] = 1
- 确定遍历顺序
2 < i <= n
1 < j < i
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
- 举例推导dp数组
。。。
class Solution {
public int integerBreak(int n) {
int dp[] = new int[n + 1];
dp[2] = 1;
for(int i = 3; i <= n; i++){
for(int j = 1; j < i; j++){
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}
}
剑指 Offer 14- II. 剪绳子 II
给你一根长度为 n
的绳子,请把绳子剪成整数长度的 m
段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1]
。请问 k[0]*k[1]*...*k[m - 1]
可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
每段长度取3最好
class Solution {
public int cuttingRope(int n) {
if(n == 2)
return 1;
if(n == 3)
return 2;
long res = 1;
while(n > 4){
//每一段取3进行累积
res *= 3;
res = res % 1000000007;
n -= 3;
}
return (int)(res * n % 1000000007);//最后一段不能被3整除,累积上再取mod
}
}
96. 不同的二叉搜索树
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
示例 2:
输入:n = 1
输出:1
- 确定dp数组(dp table)以及下标的含义
dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]。
- 确定递推公式
假设一共i
个节点,对于根节点为j
时,左子树的节点个数为j-1
,右子树的节点个数为i-j
对于根节点为j
时,其递推关系, dp[i] = ∑(1<=j<=i) dp[左子树节点数量] * dp[右子树节点数量]
,j
是头结点的元素,从1
遍历到i
为止。
所以递推公式:dp[i] += dp[j - 1] * dp[i - j];
- dp数组如何初始化
- dp[0] = 1;
- dp[1] = 1;
- 确定遍历顺序
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
}
}
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
338. 比特位计数
给你一个整数 n
,对于 0 <= i <= n
中的每个 i
,计算其二进制表示中 1
的个数 ,返回一个长度为 n + 1
的数组 ans
作为答案。
示例 1:
输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:
输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
进阶:
- 很容易就能实现时间复杂度为
O(nlogn)
的解决方案,你可以在线性时间复杂度O(n)
内用一趟扫描解决此问题吗? - 你能不使用任何内置函数解决此问题吗?(如,C++ 中的
__builtin_popcount
)
动态规划法
- 如果这个数是偶数,那么其二进制中
1
的个数一定和其1/2
的数二进制中1
的个数一样,因为1/2
就相当于右移1
位,即把偶数的最后一个0
去掉,不会影响1
的个数。res[i] = res[i / 2]
- 如果这个数是奇数:那么其二进制中
1
的个数一定是其上一个偶数二进制1
的个数+1
,因为就相当于将上一个偶数二进制的最后1
位的0
变成1
。-
res[i] = res[i - 1] + 1
—>res[i] = res[i / 2] + 1
-
- 上述两种情况可以合并成:
res[i]
的值等于res[i/2]
的值加上i % 2
。-
res[i / 2] + (i % 2)
—>res[i >> 1] + (i & 1)
-
class Solution {
public int[] countBits(int n) {
int[] res = new int[n+1];
res[0] = 0;
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) {
// 奇数:当前奇数的1的个数一定比上一个偶数+1
res[i] = res[i - 1] + 1;
} else {
// 偶数:偶数1的个数一定和其1/2的偶数1的个数一样
res[i] = res[i / 2];
}
}
return res;
}
}
//优化
class Solution {
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 1; i <= n; i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}
}
1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n
,请返回第 n 个泰波那契数 Tn 的值。
示例 1:
输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
示例 2:
输入:n = 25
输出:1389537
class Solution {
int[] dp = new int[38]; //用于防止重复计算
public int tribonacci(int n) {
if(n == 0) return 0;
if(n <= 2) return 1;
int a = 0, b = 1, c = 1;
for(int i = 3; i <= n; i++){
int d = a + b + c;
a = b;
b = c;
c = d;
}
return c;
}
}