下面的题目是我刷的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;
}
}
