东莞电商网站公司,goz建站,中国建筑人才培训网,公司制作网站价格一、动态规划的基础知识
动态规划#xff08;Dynamic Programming#xff0c;简称DP#xff09;#xff0c;动态规划问题的一般形式就是求最值#xff0c;求解动态规划的核心问题是穷举#xff0c;动态规划中每一个状态一定是由上一个状态推导出来的。解题步骤#xff…一、动态规划的基础知识
动态规划Dynamic Programming简称DP动态规划问题的一般形式就是求最值求解动态规划的核心问题是穷举动态规划中每一个状态一定是由上一个状态推导出来的。解题步骤 确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
二、一维状态转移公式
1. 509【斐波那契数】
题目 斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给定 n 请计算 F(n) 。代码
class Solution {public int fib(int n) {//1.确定dp数组及下标含义第i个斐波那契数//2.确定递推公式即状态转移方程题中给出//3.确定如何初始化dp数组题中给出//4.确定遍历顺序题中给出//5.推导验证dp数组if(n1) return n;int[] dp new int [n1];dp[0] 0;dp[1] 1;for (int i 2; i n ; i) {dp[i] dp[i-1] dp[i-2];}return dp[n];}
}2. 70【爬楼梯】
题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢代码
class Solution {public int climbStairs(int n) {//dp数组爬第i层楼梯有几种方式//dp[i] dp[i-1]dp[i-2]//dp[1]1,dp[2]2if(n2) return n;int[] dp new int [n1];dp[1] 1;dp[2] 2;for (int i 3; i n ; i) {dp[i] dp[i-1]dp[i-2];}return dp[n];}
}3. 746【使用最小花费爬楼梯】
题目 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。代码
class Solution {public int minCostClimbingStairs(int[] cost) {//你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯//这句话表示爬到0或1是不用支付费用的但是从0或1开始爬是要花费的//dp数组表示爬到第i个台阶需要支付的最小费用//dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2])//dp[0]0,dp[1]0int[] dp new int[cost.length1];for (int i 0; i cost.length; i) {if(i0||i1) dp[i] 0;else {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}}return dp[cost.length];}
}三、二维状态转移公式
1. 62【不同路径】
题目 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。问总共有多少条不同的路径代码
class Solution {public int uniquePaths(int m, int n) {//dp表示的是到达第i行j列总共有多少路径//dp[i][j] dp[i-1][j]dp[i][j-1]//关键的是第一行和第一列的所有位置都只有一种方法int[][] dp new int[m][n];for(int i0;im;i){dp[i][0] 1;}for (int i 0; i n; i) {dp[0][i] 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];}
}2. 63【不同路径 II】
题目 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径网格中的障碍物和空位置分别用 1 和 0 来表示。代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//有障碍物的地方dp应该直接赋值为0//第一行和第1列只要遇到障碍物就停止赋值int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] dp new int[m][n];for (int i 0; i m; i) {if(obstacleGrid[i][0] 1) break;dp[i][0] 1;}for (int i 0; i n; i) {if(obstacleGrid[0][i] 1) break;dp[0][i] 1;}for (int i 1; i m; i) {for (int j 1; j n; j) {if(obstacleGrid[i][j] 1){dp[i][j] 0;}else{dp[i][j] dp[i-1][j]dp[i][j-1];}}}return dp[m-1][n-1];}
}3. 96【不同的二叉搜索树】
题目 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。代码
class Solution {public int numTrees(int n) {//dp表示节点值从1到n组成的不同的BST数rp表示由n个节点组成且根节点为i的BST数//从每个节点组成的树的角度dp[i]rp[1]rp[2]...rp[i-1]rp[i]//从树的左右子树角度rp[i]dp[i-1]*dp[n-i]//所以dp[i]dp[1-1]*dp[n-1]...dp[i-1]*dp[i-i]//初始化dp[1]dp[0]*dp[0],dp[0]1int[] dp new int[n1];dp[0] 1;for(int i1;in;i){for(int j1;ji;j){dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
}
