DP刷题练习（一）

int fib(int n) {int dp[31];//dp[i]表示第i个数的值dp[0]=0,dp[1]=1;for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];return dp[n];}

int climbStairs(int n) {int dp[46];//dp[i]表示，爬到第i层楼梯，有dp[i]种方案dp[1]=1,dp[2]=2;for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];return dp[n];}
//递推公式怎么来？
//你想上到第10层，那你前一步是什么？
//肯定你是从第9层爬一步或者是从第8层爬两步上来，那么爬上第10层的方案就是，爬上第9层的方案+爬上第8层的方案
//∴dp[i]=dp[i-1]+dp[i-2],将最初始的dp[1]=1,dp[2]=2;

int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();int dp[n+1];//dp[i]表示，爬到第i层的最小花费dp[0]=0,dp[1]=0;//如果是爬到0/1就不用钱，因为0/1都可以作为初始点for(int i=2;i<=n;i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];//顶楼是n}//要注意题目的要求，题目是说，你一次花费当下这一层，注意是当层！的钱，你就可以向上爬1/2层
//所以你爬到第i层，可以是从i-1层来花费cost[i-1]，也可以是从i-2层来花费cost[i-2],二者取最小值就是爬上第i层的最小花费
//所以递推公式就是 dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
//要注意dp数组的初始化，你可以选择从第0层和第1层开始爬，所以爬到第0/1层的花费都是0

 int uniquePaths(int m, int n) {int dp[m][n];//dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数dp[0][0]=1;for(int i=1;i<=n-1;i++) dp[0][i]=1;for(int i=1;i<=m-1;i++) dp[i][0]=1;for(int i=1;i<=m-1;i++){for(int j=1;j<=n-1;j++) dp[i][j]=dp[i-1][j]+dp[i][j-1];}return dp[m-1][n-1];}
//动态规划五步曲
//dp含义：dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数//递推公式；dp[i][j]=dp[i-1][j]+dp[i][j-1],为什么是这样，你想，你每一步只能从上方一格，或者是左方一格走来
//那么这一格的方案数，不就是上方一格的dp[i-1][j]加上左方一格的dp[i][j-1]//初始化：你想第一行往右的这一排，是不是只能从第一格往右走走到，那他们的路径数不就只能是从左往右吗？所以初始化为1
//同理你你一列往下这一排只能从第一格往下走走到，那他们的路径数不就只能是从上往下吗？所以初始化为1
//那对于(0,0)呢？也是只能是1，你不走就已经到达终点不也是一种方案吗？//遍历顺序：自不必多说，先知道前面的才能知道后面的，所以是从前往后遍历

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();//获取行和列的长度if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;//如果障碍物在起点或者终点，那路径数无论如何都是0int dp[m+10][n+10];dp[0][0]=1;int i;for(i=1;i<=n-1;i++){//行初始化if(obstacleGrid[0][i]==0) dp[0][i]=1;else break;}for(int j=i;j<=n-1;j++) dp[0][j]=0;
//for(i=1;i<=m-1;i++){//列初始化if(obstacleGrid[i][0]==0) dp[i][0]=1;else break;}for(int j=i;j<=m-1;j++) dp[j][0]=0;
/for(int j=1;j<=m-1;j++){for(int k=1;k<=n-1;k++){if(obstacleGrid[j][k]==0) dp[j][k]=dp[j-1][k]+dp[j][k-1];else dp[j][k]=0;}}return dp[m-1][n-1];}//别看本题代码写的如此多，其实并不复杂，我们一步一步来分析
//还是动规五步曲，在这里我设obs为障碍物数组
//dp含义：dp[i][j]表示从(0,0)->(i,j)的不同路径数//递推公式：①obs[i][j]==0时 dp[i][j]=dp[i-1][j]+dp[i][j-1]
//         ②obs[i][j]==1时 dp[i][j]=0//初始化：以上两步和上道题大同小异，本题初始化才是最讲究的部分
//首先如果终点或者起点就已经是障碍物了，那么肯定出发不了，肯定到达不了，路径数就是0，直接返回0即可
//其次第一行和第一列依然是最特殊的，在没有遇到障碍物之前，第一行/列上的这些点都是可达的，直接初始化dp[0][i]/dp[i][0]=1
//但是一旦遇到了障碍物，那么障碍物后面点都是不可达的，为什么？不要忘记了题目说的，你只能向右或者向下走！所以第一行只能从右来
//你一旦遇到障碍物，后面就不能到达了，同理，第一列也一样
//所以一旦遇到障碍物，我们就初始化障碍物的位置及其后面的位置的方案数为0！！！//遍历顺序：自然也是从前往后，因为只有前面的先知道了，后面的才能知道！！！！！

数的拆分是dp中常见的类型

1.dp数组的含义：dp[i]表示，将i拆分，得到的最大值为dp[i]

2.递推公式：我们固定j（从1开始枚举到i-1），那么针对每一种情况，我们都可以将其拆分为2个数，或者是n个数的乘积

为什么这样分呢?因为拆成两个数是最基本的，n个数可以递归得到

int a=j*(i-j);//拆两个数
int b=j*dp[i-j];//拆两个数以上，递归思想！
//所以我的递推公式就是
dp[i]=max(dp[i],max(a,b));
//为什么要将dp[i]也放进来比较，因为我们是枚举j，也就是枚举拆分的第一位数！这有多种情况，而我们要的是最大的那个！

3.初始化：

0与1不必说，不用拆分，自然初始化为0

dp[2]=1,的话无法用之前的基础步得到，所以2也得初始化

//3可以拆成，1*2，1*dp[2]，2*1，2*dp[1] 所以3可以由之前的情况得到故3不用初始化dp[0]=0,dp[1]=0;//无法拆分dp[2]=1;//只能拆1*1

4.遍历顺序：自是从前往后，先知道前面的才能知道后面的

 int integerBreak(int n) {int dp[n+10];memset(dp,0,sizeof(dp));//注意这里先给所有赋值为0，因为我们一开始用dp[i]去比较，dp[i]中是没有值的，这样会报错dp[0]=0,dp[1]=0;//无法拆分dp[2]=1;//只能拆1*1for(int i=3;i<=n;i++){for(int j=1;j<i;j++){int a=j*(i-j);//拆两个数int b=j*dp[i-j];//拆两个数以上，递归思想！dp[i]=max(dp[i],max(a,b));}}return dp[n];}

小优化：

我们将数拆分，然后要使拆分后这些数的乘积最大，那么我们就要尽量使这些数相等，所以你拆一半就够了，后面你拆数就是向着大小差异的极端去的，所以可以这样优化

for(int j=1;j<=i/2;j++)

int integerBreak(int n) {int dp[n+10];memset(dp,0,sizeof(dp));dp[0]=0,dp[1]=0;//无法拆分dp[2]=1;//只能拆1*1for(int i=3;i<=n;i++){for(int j=1;j<=i/2;j++){int a=j*(i-j);//拆两个数int b=j*dp[i-j];//拆两个数以上，递归思想！dp[i]=max(dp[i],max(a,b));}}return dp[n];}

首先何为二叉搜索树，节点的要求是针对于顶点来说，顶点左侧要小于顶点，顶点的右侧要大于顶点，就是要满足左小右大

1.dp数组的含义：dp[i]，表示节点数目为i时，共有dp[i]种不同的二叉搜索树

2.递推公式：我们先用i枚举节点个数，用j表示j节点作为二叉搜索树的顶点为j，那么想想看，我们如何计算以j为顶点的二叉搜索树的种数呢？

是不是左子树的种数*右子树的种数，那么左子树有几种？是不是dp[j-1]种，你就想一串数，1，2，3，4，5此时j=4，那么比4小的，不就只有3个节点，而比4大的，不就是节点总数i，减掉j，5-4=1

然后j，有i种情况，就是说每个节点都可以作为顶点，所以都要把这i种情况累加起来

于是状态转移方程：dp[i]+=dp[j-1]*dp[i-j]

3.初始化：dp[0]=1,为什么？空树也是二叉搜索树！！

dp[1]要不要初始化？dp[1]+=dp[0]*dp[0]=1,符合现实情况，可以由递推公式得到，所以不用初始化

int numTrees(int n) {int dp[n+10];//表示i个节点，有dp[i]种不同的二叉搜索树memset(dp,0,sizeof(dp));//因为一会要自加，所以先给初值赋0dp[0]=1;//空树也是二叉搜索树for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];//dp[j-1]左子树总数}                          //dp[i-j]右子树总数}return dp[n];}

class Solution {
public:bool canPartition(vector<int>& nums) {int n=0;//背包容量int sum=0;int m=nums.size();//物品数量for(int i=0;i<m;i++) sum+=nums[i];n=sum/2;if(sum-n!=n) return false;//特判，不可能等分的情况int dp[m][n+1];//dp[i][j]针对前（0-i）个物品用容量j的背包来存放能否放满//初始化for(int i=0;i<m;i++) dp[i][0]=0;//容量为0什么都放不了for(int i=0;i<=n;i++){//第0个物品放置情况if(i>=nums[0]) dp[0][i]=nums[0];else dp[0][i]=0;}for(int i=1;i<m;i++){//物品for(int j=1;j<=n;j++){//容量if(j>=nums[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);else dp[i][j]=dp[i-1][j];}}if(dp[m-1][n]==n) return true;else return false;}
};

0/1背包要注意，所有的物品只能选择一次！！！