动态规划基础

动态规划基础

某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态是从上一个状态推导出来的。与贪心不同，贪心没有状态推导，从局部中直接选取最优解。

动态规划五部曲：

1. 确定dp数组以及下标的含义
2. 确定递推公式
3. dp数组的初始化
4. 确定遍历顺序
5. 举例推导dp数组

example:

leetcode 509

计算斐波那契数列f(n),我们按照上述五部曲的顺序来确定

1. 确定dp数组以及下标的含义：dp[i]定义为第i个数的斐波那契数值是dp[i]
2. 确定递推公式:递推公式已经由斐波那契数列的性质给出：dp[i]=dp[i-1]+dp[i-2]
3. dp数组的初始化:题目中已告知,dp[0]=0,dp[1]=1
4. 确定遍历顺序：由于第i个数值依赖于第i-1和第i-2个数值，因此遍历顺序是从前到后遍历
5. 举例推导dp数组： 0 1 1 2 3 5 8 13......

class Solution{
public:
    int fib(int N){
        if(N <= 1){
            return N;
        }
        vector<int> dp(N+1);//确定dp数组
        dp[0]=0;
        dp[1]=1;//初始化递推数组
        for(int i=2;i<=N;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }//遍历顺序
        return dp[N];
    }
};

使用最小花费爬楼梯：

leetcode746

1.确定dp数组以及下标的含义

dp[i]:到达第i阶台阶所花费的最小体力为dp[i]

2.确定递推公式

对于dp[i]的获取，有两个途径，即

dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

3.初始化dp数组 dp[0]=0 dp[1]=0

4.遍历顺序：从前向后遍历

class Solution{
public:
    int minCostClimbingStairs(vector<int>& cost){
        vector<int> dp(cost.size()+1);
        dp[0]=0;
        dp[1]=0;
        for(int i = 2;i <= cost.size();i++){
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.size()];
    }
}

整数拆分：

leetcode 343

这个题目的难处在于递推公式的确定，我们仍然按照dp的五步方法去做:

1. 确定dp数组，dp[i]表示对数字i的分拆，得到最大乘积dp[i]
2. 确定递推公式，由于是将正整数拆分为至少两个整数相乘，考虑到动态规划本就是当前状态由之前的状态递推出，因此我们需要考虑将整数拆分为两个整数相乘或者两个以上的整数相乘，因此：j为从1遍历到i-1,dp[i]从j * (i-j)和 j *dp[i-j]中选择，对j的拆分在遍历过程就实现了。
3. 初始化dp数组，dp[0]与dp[1]无意义，初始化dp[2]=1即可
4. 遍历顺序从前到后

代码为

class Solution{
public:
    int integerBreak(int n){
        vector<int> dp(n+1,0);
        dp[2]=1;
        for(int i=3;i<=n;i++){
			for(int j=1;j < i-1;j++){
            //考虑到拆分一个数使其乘积最大，一定是拆分近似相同的子数，即至少拆分为两个近似相同的数字，故此处for可写为for(int j=1;j<=i/2;j++)
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

不同路径：

leetcode62

1.确定dp数组含义:dp[i] [j]表示从(0,0)出发，到(i,j)有dp[i] [j]条不同的路径

2.确定递推公式：对于dp[i] [j],只可能是从两个方向移动过来，即

dp[i] [j]=dp [i-1] [j]+dp[i] [j-1]

3.初始化dp数组：显然dp[i] [0]一定为1，而dp[0] [j]也一定为1

class Solution{
public:
    int uniquePaths(int m, int n){
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
			dp[i][0]=1;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=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];
    }
};
//时间复杂度O(m*n)
//空间复杂度O(m*n)

//空间优化：利用一维数组，去逐行更新从(0,0)到达(i,j)的路径数
class Solution{
public:
    int uniquePaths(int m,int n){
        vector<int> dp(n,0);
        for(int i=0;i<n;i++) dp[i]=1;
        for(int j=1;i<m;j++){
			for(int i=0;i<n;i++){
				dp[i] += dp[i-1]//dp[i]=dp[i]+dp[i-1]，这就包含了从上方和从左方来的路径和
            }
        }
        return dp[n-1];
    }
};

不同的二叉搜索树

leetcode96

首先定义dp[i],dp[i]表示i个节点组成的搜索二叉树共有dp[i]种

直观来看，容易推导dp[1]=1,dp[2]=2,找到重叠子问题，dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量,故有

dp[3]=dp[2] dp[0]+dp[1] * dp[1]+dp[0]dp[2]

class Solution{
public:
    int numTrees(int n){
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int i = 1;i<=n;i++){
            for(int j=0;j<i;j++){
                dp[i] += dp[j]*dp[i-1-j]
            }
        }
        return dp[n];
    }
};