动态规划专题
相关信息
此处记录动态规划相关的题目,主要来自力扣。
力扣-Easy
lc-1646 Easy
数据范围为0-100,直接使用递推公式模拟即可。
由题目可得出:最大值肯定是在奇数位上。为了便于计算,如果n是奇数则n+1(变成偶数),多加了一个偶数位,答案不受影响。
这样处理后,for循环就可以只循环一半。
public int getMaximumGenerated(int n) {
if (n < 2) return n;
n += (n&1);
int[] ints = new int[n+1];
ints[1] = 1;
int tmp = 0, max = 1, half = n>>1;
for (int i = 1; i < half; i++) {
ints[i<<1] = ints[i];
ints[(i<<1)+1] = ints[i] + ints[i+1];
}
return Arrays.stream(ints).max().getAsInt();
}
lc-1137-第 N 个泰波那契数 Easy
直接模拟。时间复杂度为n,空间复杂度为1。
public int tribonacci(int n) {
if (n == 0) return 0;
if (n < 3) return 1;
int p1 = 0, p2 = 1, p3 = 1;
int cur = 0;
for (int i = 3; i <= n; i++) {
cur = p1 + p2 + p3;
p1 = p2;
p2 = p3;
p3 = cur;
}
return cur;
}
lc-70-爬楼梯 Easy
假设你正在爬楼梯。需要
n
阶你才能到达楼顶。每次你可以爬
1
或2
个台阶。你有多少种不同的方法可以爬到楼顶呢?
定义一个长度为n的int数组dp,dp[i]表示走到第i层时的方法数,那么,dp[i] = dp[i-1] + dp[i-2]。也就是说,到达第i层,只能从i-1或i-2层。那么其方法数就是后面这两个方法数之和。
根据题意可以得知,dp[0] = 1, dp[1] = 1。后面的值的就可以通过公式得到。
优化:由于dp[i] 只和 dp[i-1]、dp[i-2]相关,可以不用数组,使用有限的几个变量即可。
public int climbStairs(int n) {
if (n <2) return 1;
int p0 = 1, p1 = 1, p2 = 2;
for (int i = 2; i < n; i++) {
p2 = p0 + p1;
p0 = p1;
p1 = p2;
}
return p0 + p1;
}
lc-118-杨辉三角 Easy
由题意可易得,从第三行开始,除了开始和末尾的位置上的元素,其余位置上的元素都是由上方的元素以及上方左侧的元素相加得到的,此时就很容易的到从第三行开始状态转移方程为dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
。再判断下边界条件即可。
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> out = new LinkedList<>();
out.add(Arrays.asList(1));
if (numRows == 1) return out;
out.add(Arrays.asList(1,1));
int tmp;
for (int i = 3; i <= numRows; i++) {
tmp = 0;
List<Integer> in = new ArrayList<>(3);
in.add(1);
List<Integer> pre = out.get(i - 2);
// 第i行,需要使用上一行列表的除了最后一个的数。由于下标是从0开始,而行号从1开始,因此上行使用out.get(i - 2)。
for (int j = 0; j < pre.size()-1; j++) {
in.add(pre.get(tmp) + pre.get(++tmp));
}
in.add(1);
out.add(in);
}
return out;
}
lc-121-买卖股票的最佳时机 Easy
由题意可易得,从第2个元素开始,我们都需要找到之前元素中的最小值,且这个值必须小于当前值。使用dp数组来表示对于第i位元素,前面的元素中的最小值。
public int maxProfit(int[] prices) {
int len = prices.length;
int[] dp = new int[len];
if (len < 2) {
return 0;
}
dp[0] = prices[0];
dp[1] = prices[0];
int max = Math.max(0, prices[1] - prices[0]);
for (int i = 2; i < len; i++) {
dp[i] = Math.min(prices[i-1], dp[i-1]);
max = Math.max(max , prices[i] - dp[i]);
}
return max;
}
进一步优化,使用单个变量代替dp数组:
public int maxProfit(int[] prices) {
int len = prices.length;
if (len < 2) {
return 0;
}
int minValue = Math.min(prices[0], prices[1]);
int max = Math.max(0, prices[1] - prices[0]);
for (int i = 2; i < len; i++) {
minValue = Math.min(prices[i-1], minValue);
max = Math.max(max , prices[i] - minValue);
}
return max;
}
还可以进一步优化,如下所示:
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int max = 0;//最大利润
for (int i = 0; i < prices.length; i++) {
if(prices[i] < min){
min = prices[i];
}else if(prices[i] - min > max){
max = prices[i] - min;
}
}
return max;
}
lc-338-比特位计数 Easy
经过分析,可以得知:
- 奇数i的二进制表示中的1,等于前面那个数的二进制表示中的1的个数+1。
- 偶数,等于其除以2的数的二进制表示中的1的个数。
public int[] countBits(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
int flag = 0;
for (int i = 1; i <= n; i++, flag ^=1) {
if (flag == 0) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = dp[i>>1];
}
}
return dp;
}
可以进行优化。我们可以得知,i为奇数时,dp[i] = dp[i-1] + 1; 其中 i-1 为偶数,那么 dp[i-1] 就等于 dp[i>>1]。
优化后代码如下.flag的值会在0和1之间切换。
public int[] countBits(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
int flag = 1;
for (int i = 1; i <= n; i++, flag ^=1) {
dp[i] = dp[i>>1] + flag;
}
return dp;
}
LCP-07-传递信息 Easy
个人认为,这道题使用动态规划解法时,应该属于mid难度。
- 定义动态规划的状态
dp[i][j]
为经过 i 轮传递到编号 j 的玩家的方案数,可知dp[0][0]= 1
。 - 对于传信息的关系 [src, dst],如果第 i 轮传递到编号 src 的玩家,则第 i + 1 轮可以从编号 src 的玩家传递到编号 dst 的玩家。因此在计算
dp[i+1][dst]
时,需要考虑可以传递到dst的所有玩家,即下方代码处应使用累加的方式计算。
public int numWays(int n, int[][] relation, int k) {
int[][] dp = new int[k + 1][n];
dp[0][0] = 1;
for (int i = 0; i < k; i++) {
for (int[] edge : relation) {
int src = edge[0], dst = edge[1];
dp[i + 1][dst] += dp[i][src];
}
}
return dp[k][n - 1];
}
LC-1749-任意子数组和的绝对值的最大值 Easy
个人认为,这道题使用动态规划解法时,应该属于mid难度。
- 定义动态规划的状态
dp[i][j]
为经过 i 轮传递到编号 j 的玩家的方案数,可知dp[0][0]= 1
。 - 对于传信息的关系 [src, dst],如果第 i 轮传递到编号 src 的玩家,则第 i + 1 轮可以从编号 src 的玩家传递到编号 dst 的玩家。因此在计算
dp[i+1][dst]
时,需要考虑可以传递到dst的所有玩家,即下方代码处应使用累加的方式计算。
public int numWays(int n, int[][] relation, int k) {
int[][] dp = new int[k + 1][n];
dp[0][0] = 1;
for (int i = 0; i < k; i++) {
for (int[] edge : relation) {
int src = edge[0], dst = edge[1];
dp[i + 1][dst] += dp[i][src];
}
}
return dp[k][n - 1];
}
背包问题
相关信息
如果按照常见的「背包问题」的题型来抽象模型的话,「背包问题」大概是对应这样的一类问题:
泛指一类「给定价值与成本」,同时「限定决策规则」,在这样的条件下,如何实现价值最大化的问题。
参考资料:
- 宫水三叶的刷题笔记#背包问题
- 背包九讲(待bu'c)
01背包
有 N 件物品和一个容量是 V 的背包。每件物品有且只有一件。
第 i 件物品的体积是 v[i],价值是w[i]。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
示例 1:
输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3] 输出: 4 解释: 只选第一件物品,可使价值最大。
示例 2:
输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3] 输出: 5 解释: 不选第一件物品,选择第二件和第三件物品,可使价值最大。
根据变化参数和返回值,可以抽象出我们的 dp 数组:一个二维数组,其中一维代表「当前枚举到哪件物品」,另外一维代表「现在已使用的容量」,数组装的是「最大价值」。
我们只需要考虑第 i 件物品如何选择即可,对于第 i 件物品,我们有「选」和「不选」两种决策。如果不选,其实就是dp[i-1][c]
,等于我们只考虑前 i-1 件物品,当前容量为 c 的情况下的最大价值;如果选,表示新消耗了v[i]的容量,获得了w[i]的价值,那前 i-1 件物品可用的容量就成了c-v[i]。即最大价值为:dp[i-1][c-v[i]]+w[i]
。选第 i 件物品的前提是,当前剩余的背包容量>=物品体积。
在「选」和「不选」之间取最大值,就是我们「考虑前 i 件物品,使用容量不超过 C」的条件下的「背包最大价值」。
即可得「状态转移方程」为: $$ dp[i][c] = max(dp[i-1][c], dp[i-1][c-v[i]] + w[i]) $$ 代码:
public int maxValue(int N, int C, int[] v, int[] w) {
int[][] dp = new int[N][C+1];
// 先处理「考虑第一件物品」的情况。i为使用的空间,如果其>=第一件物品需要的容量,当前最大价值就为w[0],否则表示当前不装,最大价值为0。
for (int i = 0; i <= C; i++) {
dp[0][i] = i >= v[0] ? w[0] : 0;
}
// 再处理「考虑其余物品」的情况。i代表当前物品,j代表当前可以使用的容量,即剩余容量。
for (int i = 1; i < N; i++) {
for (int j = 0; j <= C; j++) {
// 不选该物品时的总价值
int n = dp[i-1][j];
// 选择该物品时的总价值,前提「剩余容量」大于等于「物品体积」
int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : n;
dp[i][j] = Math.max(n, y);
}
}
return dp[N-1][C];
}
参考
- 0很棒
- 0不错
- 0一般
- 0???