版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434732
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
水题,思路题目已经告诉你,不需要自己找递推式。
public class SolutionDay02_P3176 {
static int N = 350;
static int[][] dp = new int[N][N];
static int[][] score = new int[N][N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 0; i < n; i++){
for (int j = 0; j <= i; j++){
score[i][j] = in.nextInt();
}
}
dp[0][0] = score[0][0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0){
dp[i][0] = dp[i-1][0] + score[i][j];
continue;
}
if (j == i){
dp[i][j] = dp[i-1][j-1] + score[i][j];
continue;
}
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + score[i][j];
}
}
int max = 0;
for (int j = 0; j < n; j++){
max = Math.max(max,dp[n-1][j]);
}
System.out.println(max);
in.close();
}
递推式:
i 偶数: dp[i] = dp[i/2] + dp[i-1];
i 奇数: dp[i] = dp[i-1];
递推思路,i
递增后,相当于把所有的1
加在了最前方,而当i
为奇数时,无法构成新的2的幂,当i
为偶数时,能多出一部分解,而多出的那部分解即为dp[i/2]
的值。
public class SolutionDay02_P2229 {
static int MAX_N = 1000000;
static int[] dp = new int[MAX_N+1];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
dp[0] = 1;
for (int i = 1; i <= n;i++){
if ((i & 0x01) == 0){
dp[i] = dp[i/2];
}
dp[i] += dp[i-1];
dp[i] %= 1000000000;
}
System.out.println(dp[n]);
in.close();
}
}
O(n)O(n)阶段,多状态问题。注意阶段和状态的区分。状态:
int[][][] dp = new int[T][W][P];
表示在第T
阶段,现状态为移动了W
次且在位置P
处的最优解。
那么无非就是在一个阶段中30*2 = 60
种状态下取最优。递推式分为四种情况:
//1. 当前不移动,且能吃到苹果 (停留在原地,为了吃苹果)
//2. 移动,且吃不到当前苹果 (为了后续最大考虑,虽然吃不到当前苹果,但没准未来是最优的选择之一)
//3. 当前不移动,且吃不到当前苹果 (同2)
//4. 移动,且能吃到苹果 (切换树,为了吃苹果)
简单来说,就是对这四种情况的状态都得存下,为了后续求解最优。代码如下:
public class SolutionDay02_P2385 {
static int MAX_T = 1000;
//防止dp越界
static int[][][] dp = new int[MAX_T][32][2];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
int W = in.nextInt();
int[] nums = new int[T];
for (int i = 0; i < T; i++){
nums[i] = in.nextInt();
}
// int[] nums = {2,1,1,2,2,1,1};
// int W = 2;
//阶段0 移动0次 位置1时 最大值
dp[0][0][0] = nums[0] == 1 ? 1 : 0;
//阶段0 移动1次 位置2时 最大值
dp[0][1][1] = nums[0] == 1 ? 0 : 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j <= W; j++) {
for (int k = 1; k <= 2; k++) {
if (k == nums[i]){
// not move and eat
dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1] + 1);
// move and not eat
dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]);
}else{
// not move and not eat
dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1]);
// move and eat
dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]+1);
}
}
}
}
System.out.println(Math.max(dp[nums.length-1][W][0],dp[nums.length-1][W][1]));
}
private static int move (int n){
return n == 1 ? 2 : 1;
}
}
最大值产生在生成过程当中,递推式相当简单。
dp[i] = Math.max(dp[i],dp[j]+efficiency[i])
但该递推式需要符合j.endTime + R >= i.startTime
,代码如下:
public class SolutionDay02_P3616 {
static int MAX_M = 1000;
static int[] dp = new int[MAX_M];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int R = in.nextInt();
Interval[] intervals = new Interval[M];
for (int i = 0; i < M; i++){
int start = in.nextInt();
int end = in.nextInt();
int eff = in.nextInt();
intervals[i] = new Interval(start, end, eff);
}
// int M = 4;
// int R = 2;
// Interval[] intervals = new Interval[M];
// intervals[0] = new Interval(1, 2, 8);
// intervals[1] = new Interval(10, 12, 19);
// intervals[2] = new Interval(3, 6, 24);
// intervals[3] = new Interval(7, 10, 31);
Arrays.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start != o2.start ? o1.start-o2.start : o1.end - o2.end;
}
});
for (int i = 0; i < M; i++){
dp[i] = intervals[i].efficiency;
for (int j = 0; j < i; j++){
if (intervals[j].end + R <= intervals[i].start){
dp[i] = Math.max(dp[i],intervals[i].efficiency+dp[j]);
}
}
}
int max = 0;
for (int i = 0; i < M; i++){
max = Math.max(max, dp[i]);
}
System.out.println(max);
in.close();
}
}
class Interval{
int start;
int end;
int efficiency;
Interval(int start,int end,int efficiency){
this.start = start;
this.end = end;
this.efficiency = efficiency;
}
}
区间DP,在做leetcode时,也遇到了很多相关的回文DP,题目的意思是让我们求删和加得到最新回文的代价最小。
3 4
abcb
a 1000 1100
b 350 700
c 200 800
如abcb
有很多种做法如1. abcba 2. bcbabcb
,在这里显然bcbabca
最小。
主要思想:
i = 0
ab 删a -> b 加a -> aba
abc 删a -> bc 加a -> abca
abcb 删a -> bcb 加a -> abcba
## "bc"可以被看成已经进行回文操作。
j = M - 1
ab 删b -> a 加b -> bab
abc 删c -> ab 加c -> cabc
abcb 删b -> abc 加b -> babcb
## "ab","abc"均可以被看成已经进行回文操作。
ss[i] == ss[j]
)
首尾元素相等,可以忽略不看。public class SolutionDay02_P3280 {
static int[] cost = new int[26];
//static int[][] dp = new int[2048][2048];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
String s = in.next();
int[][] dp = new int[M][M];
for (int i = 0; i < N; i++){
char c = in.next().charAt(0);
int add = in.nextInt();
int delete = in.nextInt();
cost[c-'a'] = Math.min(add, delete);
}
// int N = 3;
// int M = 4;
// String s = "abcb";
//
// cost[0] = 1000;
// cost[1] = 350;
// cost[2] = 200;
char[] ss = s.toCharArray();
for (int i = M - 1; i >= 0; i--) {
for (int j = i + 1; j < M; j++) {
dp[i][j] = Math.min(dp[i + 1][j] + cost[ss[i] - 'a'],
dp[i][j - 1] + cost[ss[j] - 'a']);
if (ss[i] == ss[j]) {
dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
}
}
}
System.out.println(dp[0][M-1]);
}
}