算法动态规划
hiriki斐波拉契数
leetcode题目链接
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int fib(int n) {
if(n<=1){
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-2] + dp[i-1];
}
return dp[n];
}
}
|
爬楼梯
leetcode题目链接
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int climbStairs(int n) {
if(n<=2){
return n;
}
int[] dp = new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i = 3;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
|
使用最小花费爬楼梯
leetcode题目链接
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length+1];
dp[0]=0;
dp[1]=0;
for(int i=2;i<dp.length;i++){
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[dp.length-1];
}
}
|
不同路径
leetcode题目链接
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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 j = 0;j<n;j++){
dp[0][j] = 1;
}
for(int i = 1;i<m;i++){
for(int j = 1;j<n;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
|
不同路径II
leetcode题目链接
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1){
return 0;
}
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];
} else {
dp[i][j]=0;
}
}
}
return dp[m-1][n-1];
}
}
|
整数拆分
leetcode题目链接
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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/2+1;j++){
dp[i] = Math.max(Math.max(j*(i-j),j*dp[i-j]),dp[i]);
}
}
return dp[n];
}
}
|
不同的二叉搜索树
leetcode题目链接
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=i;j++){
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}
|
0-1 背包（二维数组）
背包最大重量为4。
物品为：
|
重量 |
价值 |
| 物品0 |
1 |
15 |
| 物品1 |
3 |
20 |
| 物品2 |
4 |
30 |
问背包能背的物品最大价值是多少？
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public class BagProblem {
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
int goods = weight.length;
int[][] dp = new int[goods][bagSize+1];
for(int j = 0;j<weight[0];j++){
dp[0][j] = 0;
}
for(int j = weight[0];j<=bagSize;j++){
dp[0][j] = value[0];
}
for(int i = 1; i < goods; i++){
for(int j = 1; j <= bagSize; j++){
if(j < weight[i]){
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
}
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
}
|
0-1 背包（滚动数组）
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
|
分割等和子集(0-1背包是否存在、装满)
leetcode题目链接
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路草稿
题解
滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public boolean canPartition(int[] nums) {
if(nums==null||nums.length==0){
return false;
}
int sum = 0;
for(int num:nums){
sum+=num;
}
if(sum%2==1){
return false;
}
int target = sum/2;
int[] dp = new int[target+1];
for(int i = 0;i<nums.length;i++){
for(int j = target;j>=nums[i];j--){
dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[target]==target;
}
}
|
二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| public class Solution {
public static void main(String[] args) {
int num[] = {1,5,11,5};
canPartition(num);
}
public static boolean canPartition(int[] nums) {
int len = nums.length;
int sum = 0;
for (int num : nums) {
sum += num;
}
if ((sum %2 ) != 0) {
return false;
}
int target = sum / 2;
boolean[][] dp = new boolean[len][target + 1];
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
for (int i = 1; i < len; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (nums[i] == j) {
dp[i][j] = true;
continue;
}
if (nums[i] < j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
for (int i = 0; i < len; i++) {
for (int j = 0; j <= target; j++) {
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
return dp[len - 1][target];
}
}
false true false false false false false false false false false false
false true false false false true true false false false false false
false true false false false true true false false false false true
false true false false false true true false false false true true
|
最后一块石头的重量II(0-1背包最多能装多少)
leetcode题目链接
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
思路草稿
题解
滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int stone:stones){
sum+=stone;
}
int target = sum/2;
int[] dp = new int[target+1];
for(int i = 0;i<stones.length;i++){
for(int j = target;j>=stones[i];j--){
dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum - dp[target]-dp[target];
}
}
|
二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int s : stones) {
sum += s;
}
int target = sum / 2;
int[][] dp = new int[stones.length][target + 1];
for (int j = stones[0]; j <= target; j++) {
dp[0][j] = stones[0];
}
for (int i = 1; i < stones.length; i++) {
for (int j = 1; j <= target; j++) {
if (j >= stones[i]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[stones.length - 1][target]);
return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];
}
}
|
目标和(0-1背包装满多少种装法)
leetcode题目链接
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int num:nums){
sum+=num;
}
if(target<0&&sum<-target){
return 0;
}
if((target+sum)%2!=0){
return 0;
}
int size = (target+sum)/2;
if(size<0){
size = -size;
}
int[] dp = new int[size+1];
dp[0]=1;
for(int i = 0;i<nums.length;i++){
for(int j = size;j>=nums[i];j--){
dp[j] += dp[j-nums[i]];
}
}
return dp[size];
}
}
|
一和零(0-1背包装满最多有多少个物品)
leetcode题目链接
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
int oneNum,zeroNum;
for(String str : strs){
oneNum = 0;
zeroNum = 0;
for(char c : str.toCharArray()){
if(c=='0'){
zeroNum++;
} else {
oneNum++;
}
}
for(int i = m;i>=zeroNum;i--){
for(int j = n;j>=oneNum;j--){
dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
}
}
}
return dp[m][n];
}
}
|
完全背包
背包最大重量为4。
物品为：
|
重量 |
价值 |
| 物品0 |
1 |
15 |
| 物品1 |
3 |
20 |
| 物品2 |
4 |
30 |
每个物品个数无限，问背包能背的物品最大价值是多少？
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
private static void testCompletePack(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){
for (int j = weight[i]; j <= bagWeight; j++){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
private static void testCompletePackAnotherWay(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 1; i <= bagWeight; i++){
for (int j = 0; j < weight.length; j++){
if (i - weight[j] >= 0){
dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
}
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
|
零钱兑换II（完全背包装满有多少种装法）
leetcode题目链接
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i = 0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
}
|
组合总和 IV
leetcode题目链接
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
思路草稿
整体思路和 零钱兑换II 类似，唯一不同的就是 零钱兑换II 求的是组合，而本题求的是排列。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0]=1;
for(int j = 0;j<=target;j++){
for(int i = 0;i<nums.length;i++){
if(j>=nums[i]){
dp[j] += dp[j-nums[i]];
}
}
}
return dp[target];
}
}
|
零钱兑换（完全背包装满最少有多少个物品）
leetcode题目链接
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
思路
dp数组：容量为j的背包装满最少放dp[j]个物品
递推公式：
1
| dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
|
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
dp[0] = 0 ;
for(int j = 1;j<dp.length;j++){
dp[j] = Integer.MAX_VALUE;
}
for(int i = 0;i<coins.length;i++){
for(int j = coins[i];j<=amount;j++){
if(dp[j-coins[i]]!=Integer.MAX_VALUE){
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
}
return dp[amount]==Integer.MAX_VALUE ? -1:dp[amount];
}
}
|
完全平方数
leetcode题目链接
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
思路
dp数组：容量为j的背包最少可以放dp[j]个物品
递推公式：
1
| dp[j] = Math.min(dp[j],dp[j-i*i]+1);
|
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n+1];
dp[0] = 0;
for(int j = 1;j<=n;j++){
dp[j] = max;
}
for(int i = 1 ; i*i<=n;i++){
for(int j = i*i;j<=n;j++){
if(dp[j-i*i]!=max){
dp[j] = Math.min(dp[j],dp[j-i*i]+1);
}
}
}
return dp[n];
}
}
|
单词拆分
leetcode题目链接
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i = 0;i<=s.length();i++){
for(int j = 0;j<i&&dp[i]==false;j++){
if(wordDict.contains(s.substring(j,i))&&dp[j]==true){
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
|
打家劫舍
leetcode题目链接
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int rob(int[] nums) {
if(nums.length==1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2;i<nums.length;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
}
|
打家劫舍II
leetcode题目链接
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int rob(int[] nums) {
if(nums==null||nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
return Math.max(robAction(nums,0,nums.length-2),robAction(nums,1,nums.length-1));
}
private int robAction(int[] nums,int start,int end){
if(start==end){
return nums[start];
}
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start+1] = Math.max(nums[start],nums[start+1]);
for(int i = start+2;i<=end;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[end];
}
}
|
打家劫舍III
leetcode题目链接
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int rob(TreeNode root) {
int[] res = backTracking(root);
return Math.max(res[0],res[1]);
}
private int[] backTracking(TreeNode cur){
int[] res = new int[2];
if(cur==null){
return res;
}
int[] leftDp = backTracking(cur.left);
int[] rightDp = backTracking(cur.right);
res[0] = Math.max(leftDp[0],leftDp[1])+Math.max(rightDp[0],rightDp[1]);
res[1] = cur.val+leftDp[0]+rightDp[0];
return res;
}
}
|
最长递增子序列
leetcode题目链接
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0;i<nums.length;i++){
dp[i] = 1;
}
int result = 1;
for(int i = 1;i<nums.length;i++){
for(int j = 0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
result = Math.max(dp[i],result);
}
return result;
}
}
|
最长连续递增序列
leetcode题目链接
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
思路草稿
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
for(int i = 0;i<nums.length;i++){
dp[i] = 1;
}
int result = 1;
for(int i = 1;i<nums.length;i++){
if(nums[i]>nums[i-1]){
dp[i] = dp[i-1]+1;
}
result = Math.max(dp[i],result);
}
return result;
}
}
|
