下面的题目是我刷的Leetcode上关于动态规划的题目，因为题还没刷完，所以这篇文章会将不时地进行续更

package cn.infobuy.gouqi.demo;

import java.util.List;

/**
 * 动态规划
 * @author JohnLiu
 */
public class DPSolution {
    /**
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     * @param n
     * @return
     */
    public int numTrees(int n) {
        // numThrees(n)=numThrees(i-1)*numThrees(n-i);i=[2,n-1]
        if(n<=0){
            return 0;
        }
        int[] numThrees = new int[Math.max(n+1,3)];
        numThrees[0]=1;
        numThrees[1]=1;
        numThrees[2]=2;
        for(int nodeNum=3;nodeNum<n+1;nodeNum++){
            for(int j=1;j<=nodeNum;j++){
                numThrees[nodeNum]+=numThrees[j-1]*numThrees[nodeNum-j];
            }
        }
        return numThrees[n];
    }
    
    public int minCostClimbingStairs(int[] cost) {
        // dp(n)=Math.min(dp(n-1)+cost(n-1),dp(n-2)+cost(n-2))
        int dpp1=0,dpp2=0,dpcurr=0;
        for(int i=2;i<=cost.length;i++){
            dpcurr=Math.min(dpp2+cost[i-2],dpp1+cost[i-1]);
            dpp2=dpp1;
            dpp1=dpcurr;
        }
        return dpcurr;
    }
    /**
     * 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        
        
        return -1;
    }
    /**
     * 需要 n 步你才能到达楼顶
     * 每次你可以爬 1 或 2 个台阶
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int pre2Floor=1;
        int pre1Floor=2;
        if(n==1){
            return pre2Floor;
        }else if(n==2){
            return pre1Floor;
        }
        int currentFloor=0;
        for(int i=3;i<=n;i++){
            currentFloor = pre2Floor+pre1Floor;
            pre2Floor=pre1Floor;
            pre1Floor=currentFloor;
        }
        return currentFloor;
    }
    /**
     *  m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int line = grid.length;
        int row = grid[0].length;
        int[] preLineMinPathSum = new int[row];
        //迭代第1行
        for(int i=0;i<row;i++){
            preLineMinPathSum[i]=i==0?grid[0][0]:grid[0][i]+preLineMinPathSum[i-1];
        }
        //迭代第2-n行
        int[] thisLineMinPathSum;
        for(int i=1;i<line;i++){
            thisLineMinPathSum=new int[row];
            thisLineMinPathSum[0]=preLineMinPathSum[0]+grid[i][0];
            for(int j=1;j<row;j++){
                if(thisLineMinPathSum[j-1]>preLineMinPathSum[j]){
                    thisLineMinPathSum[j]=preLineMinPathSum[j]+grid[i][j];
                }else{
                    thisLineMinPathSum[j]=thisLineMinPathSum[j-1]+grid[i][j];
                }
            }
            preLineMinPathSum=thisLineMinPathSum;
        }
        return preLineMinPathSum[row-1];
    }
    /**
     * 在有阻碍物的情况下
     * m x n 网格中从左上到右下有几种走法
     * @param m
     * @param n
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /**
         * 阻碍物(i,k)表示：f((0,0),(i,k))=0;
         */
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[] preLinePaths=new int[m];
        // 迭代第1行的所有列
        for(int i=0;i<m;i++){
            if(i==0){
                preLinePaths[i]=obstacleGrid[0][i]==1?0:1;
            }else{
                preLinePaths[i]=obstacleGrid[0][i]==1?0:preLinePaths[i-1];
            }
        }
        // 迭代第2行-第n行的所有列
        int[] thisLinePaths;
        for(int line=1;line<n;line++){//line
            thisLinePaths=new int[m];
            thisLinePaths[0]=obstacleGrid[line][0]==1?0:preLinePaths[0];
            for(int r=1;r<m;r++){//row
                thisLinePaths[r]=obstacleGrid[line][r]==1?0:thisLinePaths[r-1]+preLinePaths[r];
            }
            preLinePaths=thisLinePaths;
        }
        return preLinePaths[m-1];
    }

    /**
     * m x n 网格中从左上到右下有几种走法
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        // f(m,n)=f(m-1,n)+f(m,n-1)
        // f(0,0)=0,f(n,0)=1,f(0,n)=1
        //记录上一行的所有走法
        int[] preLinePaths=new int[m];
        int[] thisLinePaths;
        for(int i=0;i<m;i++){
            preLinePaths[i]=1;
        }
        for(int l=1;l<n;l++){//第几行 line
            thisLinePaths=new int[m];
            thisLinePaths[0]=1;
            for(int r=1;r<m;r++){//第几列 row
                thisLinePaths[r]=thisLinePaths[r-1]+preLinePaths[r];
            }
            preLinePaths=thisLinePaths;
        }
        return preLinePaths[m-1];
    }
    /**
     * 求最大子序和
     * 当数组中存在非负数的元素，最大子序和的起点一定大于0
     * @param nums
     * @return maxSum
     */
    public int maxSubArray(int[] nums) {
        int maxSum = 0;
        int thisSum = 0;
        int singleMax = nums[0];
        //假设数组中的元素存在非负数
        for(int i = 0;i<nums.length;i++){
            thisSum+=nums[i];
            if(thisSum>maxSum){
                maxSum=thisSum;
            }
            if(thisSum<0){
                thisSum=0;
            }
            if(nums[i]>singleMax){
                singleMax=nums[i];
            }
        }
        if(maxSum==0){
            //说明数组中的元素均为非正数
            return singleMax;
        }else{
            return maxSum;
        }
    }
    /**
     * 最长上升子序列
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        /**
         * 虽然求的是一个整数数组的最长上升子序列，但是dp的是，当子序列包含数组最后一个元素的LIS长度
         * int[] lis 记录截止点到index时的序列的LIS的长度
         * f(n) = Math.max(f(n-i),f(n-k),f(n-m),,,)+1 {当 nums[n]>nums[n-i],nums[n-j],nums[n-k]}
         * 时间复杂度为 O(n^2)
         * 
         */
        if(nums.length==0) {
            return 0;
        }
        int[] lis = new int[nums.length];
        lis[0]=1;
        int maxLIS = lis[0];
        for(int i=1;i<nums.length;i++) {
            lis[i]=1;
            // 这一步特别耗时，其实不需要每次都查找一遍
            // 存起来就可以
            for(int j=0;j<i;j++) {
                if(nums[i]>nums[j]) {
                    lis[i]=Math.max(lis[i], lis[j]+1);
                }
            }
            if(maxLIS<lis[i]) {
                maxLIS=lis[i];
            }
        }
        return maxLIS;
    }
    /**
     * 最大正方形
     * 备注：当dp[][]记录矩阵右上角
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        // dp[][] 记录以(x,y)为矩形右上角的边长
        int xlen = matrix.length;
        if(xlen==0) {
            return 0;
        }
        int ylen = matrix[0].length;
        int[][] dp = new int[xlen][ylen];
        int maxVas = 0;
        // 设定纵向第一列
        for(int y=0;y<ylen;y++) {
            dp[0][y]=matrix[0][y]-48;
            maxVas=Math.max(maxVas,dp[0][y]);
        }
        // 设定横向第一列
        for(int x=0;x<xlen;x++) {
            dp[x][0] = matrix[x][0]-48;
            maxVas=Math.max(maxVas,dp[x][0]);
        }
        for(int x=1;x<xlen;x++) {
            for(int y=1;y<ylen;y++) {
                if(matrix[x][y]=='1') {
                    // 状态转移
                    dp[x][y]=Math.min(Math.min(dp[x-1][y-1],dp[x-1][y]),dp[x][y-1])+1;
                    maxVas=Math.max(maxVas, dp[x][y]);
                }
            }
        }
        return maxVas*maxVas;
    }
    /**
     * 丑数 II
     * 丑数就是只包含质因数 2, 3, 5 的正整数。
     * number = 2^i*3^j*5^k (i>=0,j>=0,k>=0) 
     *  1, 2, 3, 4, 5, 6, 8, 9, 10, 12
     *  
     *  状态转移方程：f(n) = Math.min(f(i)*2,f(j)*3,f(k)*5) // i,j,k从0开始不断累加
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        int[] uglyNumbers = new int[n];
        int num_2=0;
        int num_3=0;
        int num_5=0;
        uglyNumbers[0]=1;
        for(int i=1;i<n;i++){
            uglyNumbers[i] = Math.min(Math.min(uglyNumbers[num_2]*2, uglyNumbers[num_3]*3),uglyNumbers[num_5]*5);
            if(uglyNumbers[i]==uglyNumbers[num_2]*2){
                num_2++;
            }
            if(uglyNumbers[i]==uglyNumbers[num_3]*3){
                num_3++;
            }
            if(uglyNumbers[i]==uglyNumbers[num_5]*5){
                num_5++;
            }
        }
        return uglyNumbers[n-1];
    }
    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        int line = triangle.size();
        int edge = triangle.get(line-1).size();
        int[][] dp = new int[line][edge];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<line;i++){
            List<Integer> thisLine = triangle.get(i);
            for(int j=0;j<triangle.get(i).size();j++){
                if(j==0){
                    dp[i][j]=dp[i-1][0];
                }else if(j==thisLine.size()-1){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j]);
                }
                dp[i][j]+=thisLine.get(j);
            }
        }
        int minimumTotal=Integer.MAX_VALUE;
        for(int j=0;j<dp[line-1].length;j++){
            minimumTotal=Math.min(minimumTotal,dp[line-1][j]);
        }
        return minimumTotal;
    }
    public int minimumTotal2(List<List<Integer>> triangle) {
        int line = triangle.size();
        // 自底向上保留记录的值
        // 好处1：不会覆盖之后要参与计算的值
        // 好处2：最后的dp[0]就是最小值，不需要再进行遍历得出
        int[] dp = new int[line+1];
        for(int i=line-1;i>=0;i--){
            List<Integer> thisLine = triangle.get(i);
            for(int j=0;j<=i;j++){
                dp[j]=Math.min(dp[j], dp[j+1])+thisLine.get(j);
            }
        }
        return dp[0];
    }
    /**
     * 买卖股票的最佳时机
     * 最多只允许完成一笔交易
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int[] profits = new int[prices.length-1];
        // 求出最大子序和
        int maxProfit=0;
        int tmpProfit=0;
        for(int i=0;i<profits.length;i++){
            // 求出每天的利润空间
            profits[i]=prices[i+1]-prices[i];
            tmpProfit+=profits[i];
            if(tmpProfit<0){
                tmpProfit=0;
            }else if(tmpProfit>maxProfit){
                maxProfit=tmpProfit;
            }
        }
        return maxProfit;
    }
    /**
     * 买卖股票的最佳时机 IV
     * 你最多可以完成 k 笔交易
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        
        
        return k;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}