小菜鸡想法：通过代码随想录公众号的动态规划专题进行学习与刷题！因为本人要参加四月的蓝桥杯考试，故想先掌握动态规划的技巧！自己也想留档，所以记录下来！那就开始吧！
动态规划五步骤：
- 确定dp数组以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
动态规划debug方式： dp数组打印出来
基础题(7道题)：- 斐波那契数
- 爬楼梯
- 使用最小花费爬楼梯
- 不同路径
- 不同路径 II
- 整数拆分
- 不同的二叉搜索树
dp解法：
class Solution {
public int fib(int n) {
//特殊情况
if(n<=1) return n;
//1、确定数组及其下标的含义
int dp[] =new int[n+1]; //dp代表sum,下标代表第i个元素的值
//2、递推公式
//dp[i]=dp[i-1]+dp[i-2]
//3、初始化
dp[0]=0;
dp[1]=1;
//4、确定遍历顺序
//i++
//5、举例子推到dp数组，确定对不对
//分析完毕，开始代码
for(int i=2;i<=n;i++){
dp[i]=dp[i-2]+dp[i-1];
}
return dp[n];
}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解法：(解法跟509斐波那契数解法差不多，只是看你能不能推出那个递推公式)
class Solution {
public int climbStairs(int n) {
int sum=0; //总共有几种爬法
if(n<=2) return n;
else{
int first=1; //再补爬两个楼梯
int second=2; //再补爬一个楼梯
for(int i=0;i
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
dp解法：
class Solution {
public int minCostClimbingStairs(int[] cost) {
//特殊情况
// if(n<=1) return n;
//1、确定数组及其下标的含义
int dp[] =new int[cost.length]; //dp代表最便宜消耗,下标代表到第i个元素的最小消耗
//2、递推公式
//dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
//最终比较值
//dp[n-2] dp[n-1]倒数第一跟第二进行比较
//3、初始化
//要么从0开始，要么从1开始
dp[0]=cost[0];
dp[1]=cost[1];
//4、确定遍历顺序
//i++
//5、举例子推到dp数组，确定对不对
//分析完毕，开始代码
for(int i=2;i
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
画图推导公式：
dp[i][j]=dp[i-1][j]+dp[i][j-1]
class Solution {
public int uniquePaths(int m, int n) {
//特殊情况
if(m==1||n==1) return 1;//当起点和终点为同一列时，也只有一种方法
//1、确定数组及其下标的含义
int dp[][] =new int[m][n]; //dp代表方式数量,下标代表几行第几列那个元素从起点走到终点的方式数量
//2、递推公式(画图递推！！)
//dp[i][j]=dp[i-1][j]+dp[i][j-1]
//3、初始化
dp[0][0]=0;
for(int i=1;i
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
普通动态解法：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// m,n分别表示行和列
int m = obstacleGrid.length, n = obstacleGrid[0].length;
// dp[i][j]表示从(0,0)到(i,j)所有路径的可能性
int[][] dp = new int[m][n];
// 在没有遇到障碍物前，第一列dp都为1
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
// 在没有遇到障碍物前，第一行dp都为1
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
// dp[i-1][j]和dp[i][j-1]到dp[i][j]都只需走一步就到达dp[i][j]，
// 所以dp[i][j]所有的路径可能性为dp[i-1][j]和dp[i][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];
}
}
}
return dp[m - 1][n - 1];
}
}
高级动态解法：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int n = obstacleGrid.length, m = obstacleGrid[0].length;
int[] f = new int[m];
f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (obstacleGrid[i][j] == 1) {
f[j] = 0;
continue;
}
if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
f[j] += f[j - 1];
}
}
}
return f[m - 1];
}
}
343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
class Solution {
public int integerBreak(int n) {
//特殊情况
if(n<=1) return n; //n=0 return 0;n=1 return 1
if(n==2) return 1;
if(n==3) return 2;
//1、确定数组及其下标的含义
int dp[] =new int[n+1]; //dp代表成绩最大化,下标代表第i个元素拆分后的乘积最大化
//2、递推公式
//dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
//3、初始化
//小于4的数切分会导致数更小
//所以不切分更佳
dp[0]=0;
dp[1]=1;
dp[2]=2;
dp[3]=3;
//4、确定遍历顺序
//i++
//5、举例子推到dp数组，确定对不对
//分析完毕，开始代码
for(int i=4;i
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
class Solution {
public int numTrees(int n) {
//1、确定数组及其下标的含义
int dp[] =new int[n+1]; //dp代表sum,下标代表第i个元素的值
//2、递推公式
//dp[i] =dp[i] + (dp[j-1] * dp[i-j]);
//3、初始化
dp[0]=1;
dp[1]=1;
//4、确定遍历顺序
//i++ j++
//分析完毕，开始代码
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]=dp[j-1]*dp[i-j]+dp[i];
}
}
//5、举例子推到dp数组，确定对不对
return dp[n];
}
}
基础篇over,接下来背包问题 
