提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

动态规划题解集合（Java）

JAVA 集合
2023-03-14 22:45:29 时间

持续更新中（解题思路写在代码注释里）


1、爬楼梯


假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。


示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

1.  1 阶 + 1 阶

2.  2 阶


示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1.  1 阶 + 1 阶 + 1 阶

2.  1 阶 + 2 阶

3.  2 阶 + 1 阶


public static int climbStairs(int n) {
 
        /**
         * 爬楼梯的方案数为爬到n-1阶的方案数（只剩一步到楼顶）加上爬到n-2阶的方案数（只剩一次两步到楼顶）
         * 可知符合方案数 dp[n] = dp[n-1] + dp[n-2]
         * dp[0]=0, dp[1]=1,dp[2]=2
         */
        
        if(n == 1){
            return 1;
        }
 
        int []dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        return dp[n];
    }


2、最大子序列


给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。


示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。


示例 2：

输入：nums = [1]

输出：1


示例 3：

输入：nums = [0]

输出：0


示例 4：

输入：nums = [-1]

输出：-1


示例 5：

输入：nums = [-100000]

输出：-100000

 

提示：

1 <= nums.length <= 3 * 104

-105 <= nums[i] <= 105


public static int maxSubArray(int[] nums) {
            
            
            /**
             * 方法一： 暴力枚举
             */
            //  int n = nums.length;
            //  int big = nums[0];
            //  int index1 = 0;
            //  int index2 = 0;
            //  int temp = nums[0];
            //  
            //  for(int i=0;i<n;i++) {
            //      temp = nums[i];
            //      if(temp>big) {
            //          big=temp;
            //      }
            //      index1=i;
            //      index2=i;
            //      for(int j=i+1;j<n;j++) {
            //          temp = temp+nums[j];
            //          if(temp > big) {
            //              index2 = j;
            //              big = temp;
            //          }
            //      }
            //  }
            //  
            //  System.out.println(big);
            
            
            
            
            
            /**
             * 方法二： 动态规划
             * 
             * dp[i]表示以nums[i]结尾的最大序列和
             * 当i=0时，dp[0] = nums[0]
             * 当i>0时，dp[i] = max{ (dp[i-1]+nums[i]) , nums[i] }
             * 
             * 再找出dp[]中最大即可
             */
            int []dp = new int[nums.length];
            dp[0] = nums[0];
            
            for(int i=1;i<nums.length;i++) {
                dp[i] = Math.max((dp[i-1]+nums[i]), nums[i]);
            }
            int big = dp[0];
            for(int i=1;i<dp.length;i++) {
                if(dp[i] > big) {
                    big = dp[i];
                }
            }
            
            return big;
        }


3、杨辉三角


给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。


示例 1:

输入: numRows = 5

输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]


示例 2:

输入: numRows = 1

输出: [[1]]


提示:

1 <= numRows <= 30


class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> a = new ArrayList<List<Integer>>();
        
        for(int i=0; i<numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            
            for(int j=0; j <= i; j++) {
                if(j==0 || j==i) {
                    row.add(1);
                } else {
                    row.add(a.get(i-1).get(j-1) + a.get(i-1).get(j));                   
                }
            }
            a.add(row);
        }
        return a;
    }
}



4、杨辉三角II


给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。


示例 1:

输入: rowIndex = 3

输出: [1,3,3,1]


示例 2:

输入: rowIndex = 0

输出: [1]


示例 3:

输入: rowIndex = 1

输出: [1,1]

 

提示:

0 <= rowIndex <= 33


class Solution {
    public List<Integer> getRow(int rowIndex) {
 
        int [][] a = new int[34][34];
        List<Integer> row = new ArrayList<>();
        for(int i=0; i<= rowIndex; i++) {
            for(int j=0; j<=i; j++) {
                if(j==0 || j==i) {
                    a[i][j] = 1;
                } else {
                    a[i][j] = a[i-1][j-1] + a[i-1][j];
                }
            }
        }
  
        
        for(int i=0; i<=rowIndex; i++) {
            row.add(a[rowIndex][i]);
        }
        return row;
    }
}


5、买股票的最佳时机


给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。


返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。


示例 1：

输入：[7,1,5,3,6,4]

输出：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

     

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。


示例 2：


输入：prices = [7,6,4,3,1]

输出：0

解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

 

提示：


1 <= prices.length <= 105

0 <= prices[i] <= 104


class Solution {
    //dp[i]表示在第i天卖出的价值最大值，它等于当天价值减去之前所有天的最小值
        int []dp = new int[prices.length];
        
        //用于保存最小值
        int small = prices[0];
        for(int i=1; i<prices.length; i++) {
            //如果第i-1天的价值比前面所有天的价值小，那么最小价值更新为prices[i-1]
            if(prices[i-1] < small) {
                small = prices[i-1];
            }
            dp[i] = prices[i] - small;
        }
        
        //再找出dp[]中最大值，即为股票的最大价值
        int big = dp[0];
        for (int i = 1; i < dp.length; i++) {
            if(dp[i] > big) {
                big = dp[i];
            }
        }
        
        return big;
}



相关文章