前言
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.最后一块石头的重量II
题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode)
题面:
代码:
class Solution {
public int lastStoneWeightII(int[] ss) {
int n = ss.length;
int sum = 0;
for (int i : ss) sum += i;
int t = sum / 2;
int[][] f = new int[n + 1][t + 1];
for (int i = 1; i <= n; i++) {
int x = ss[i - 1];
for (int j = 0; j <= t; j++) {
f[i][j] = f[i - 1][j];
if (j >= x) f[i][j] = Math.max(f[i][j], f[i - 1][j - x] + x);
}
}
return Math.abs(sum - f[n][t] - f[n][t]);
}
}
2.目标和
题目链接:494. 目标和 - 力扣(LeetCode)
题面:
代码:
class Solution {
private int[] nums;
private int[][] memo;
public int findTargetSumWays(int[] nums, int target) {
int s = 0;
for (int x : nums) {
s += x;
}
s -= Math.abs(target);
if (s < 0 || s % 2 == 1) {
return 0;
}
int m = s / 2; // 背包容量
this.nums = nums;
int n = nums.length;
memo = new int[n][m + 1];
for (int[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
return dfs(n - 1, m);
}
private int dfs(int i, int c) {
if (i < 0) {
return c == 0 ? 1 : 0;
}
if (memo[i][c] != -1) { // 之前计算过
return memo[i][c];
}
if (c < nums[i]) {
return memo[i][c] = dfs(i - 1, c); // 只能不选
}
return memo[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]); // 不选 + 选
}
}
后言
上面是动态规划的基本概念和部分习题,下一篇会有其他习题,希望有所帮助,一同进步,共勉!