牛客338107602号

分类

题解(16)

/ 注册

全部文章（共8篇）

题解 | #【模板】完全背包#

完全背包在理解01背包的基础上就容易做出了，01背包之所以使用倒序，是因为dp为一维数组，每次存放同一种物品只能存放一次，故采用倒序，采用正序就可能出现一个物品存放多次的情况。而正序存放的情况刚好适合完全背包问题。 import java.util.*; public class Main{ ...

动态规划 Java

2022-07-11

1 406

题解 | #【模板】01背包#

import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String[] str =...

动态规划 Java

2022-07-11

2 299

题解 | #[NOIP2001]装箱问题#

总结：本题使用动态规划 import java.util.*; public class Main{ public static void main(String arg[]){ Scanner sc = new Scanner(System.in); int...

动态规划 Java

2022-07-10

3 401

题解 | #最长公共子序列(一)#

总结：1.由于当截取字符串a从0到i,截取字符串b从0到j，此时两截取的字符串的最长公共子序列与前面的状态有关，并可写出状态转移方程，故使用动态规划可以解决。关键是想出状态转移方程。dp[i][j]= dp[i−1][j−1]+1, 当text1[i−1]=text2[j−1]时 ...

动态规划 Java

2022-07-09

0 333

题解 | #最长上升子序列(一)#

总结：计算i处的最长升序子序列len[i]，等于i之前所有的子序列（末尾元素大于arr[i])中最大子序列+1根据上述状态转换使用动态规划解决该问题。 import java.util.*; public class Main{ public static void main(String[...

动态规划 Java

2022-07-09

0 308

题解 | #三角形最小路径和#

总结：使用动态规划解决，空间复杂度可以优化，从n^2,2n,n。参考如下：https://leetcode.cn/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/ import java.ut...

动态规划 Java

2022-07-08

0 361

题解 | #跳台阶#

总结：可以使用两种方法递归和动态规划，其中动态规划避免了大量重复计算，时间复杂度更优 public class Solution { public int jumpFloor(int target) { //方法1递归（时间复杂度2^n，内部有很多重复计算） // ...

Java 动态规划

2022-07-08

0 284

题解 | #循环汉诺塔#

总结：1.本题可以使用动态规划，分为从A到B,从B到C两个状态。 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(S...

Java 动态规划

2022-07-06

1 1279