C++ 数据结构与算法（十二）（动态规划）

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，动态规划中每一个状态一定是由上一个状态推导出来的。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

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

F(0) = 0，F(1) = 1
求 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

• 时间复杂度： O ( 2 n ) O(2^n) O(2n)
• 空间复杂度：O(n)，递归调用栈

class Solution {
public:
    int fib(int N) {
        if (N < 2) return N;
        return fib(N - 1) + fib(N - 2);
    }
};

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. 确定遍历顺序：从前到后遍历
5. 举例推导dp数组

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    int fib(int n) {
        if(n < 2) return n;
        int dp[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1. dp[i]： 爬到第i层楼梯，有dp[i]种方法
2. dp[i] = dp[i - 1] + dp[i - 2];
   （上 i-1 层楼梯，有dp[i - 1]种方法，那么再一个台阶就是dp[i]；上 i-2 层楼梯，有dp[i - 2]种方法，那么再两个个台阶就是dp[i]）
3. dp[1] = 1; dp[2] = 2;
4. 从前到后遍历

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( n ) O(n) O(n)

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        int dp[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

• 空间复杂度优化： O ( 1 ) O(1) O(1)

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        int dp[3];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; ++i){	// 遍历后面的楼梯
            int sum = dp[1] + dp[2];	
            dp[1] = dp[2];				
            dp[2] = sum;			
        }
        return dp[2];
    }
};

• 扩展：一次最多能跨越m阶楼梯

class Solution {
public:
    int climbStairs(int n， int m) {	// n为最终的目标楼梯，m为一次最多能爬m阶
        if(n <= m) return m;
        int dp[n+1];
        dp[0] = 1;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){	// 前m阶内的组合
				if(i-j > 0) dp[i] += dp[i-j];
			}
        }
        return dp[n];
    }
};

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

1. dp[i]：到达第 i 阶消耗的最少体力（下标从0开始），达到楼梯顶部指下标为数组长度的阶梯；
2. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
   （分别达到前两个阶梯与该阶梯向上爬需要消耗体力的最小值）
3. 达到前两个阶梯即dp[0]、dp[1] 不需要体力值，因为从其一开始出发；
4. 从前往后遍历。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int len = cost.size();
        int dp[len+1];  
        dp[0] = 0;      // 能跨两个台阶，因此只有一个台阶时为0
        dp[1] = 0;
        for(int i = 2; i <= len; ++i){
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]); 
        }
        return dp[len];
    }
};

• 空间复杂度优化： O ( 1 ) O(1) O(1)

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        int len = cost.size();
        int dp[3];  
        dp[0] = 0;      // 能跨两个台阶，因此只有一个台阶时为0
        dp[1] = 0;
        for(int i = 2; i <= len; ++i){
            dp[2] = min(dp[1] + cost[i-1], dp[0] + cost[i-2]); 
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
    }
};

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

1. dp[ i ] [ j ] :从(0,0)出发到(i, j) 不同的路径数量；
2. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];左边和上边两个方向过来；
3. vector> dp(m+1, vector(n+1, 1));都初始化为1，下标从1开始；
4. 从左往右，一层一层遍历。

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m == 1 || n == 1) return 1;
        vector> dp(m+1, vector(n+1, 1));
        for(int i = 2; i <= m; ++i){
            for(int j = 2; j <= n; ++j){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];	// 下标从1开始
    }
};

• 空间复杂度优化：O(n)

一维数组（滚动数组），dp[j] = dp[j-1] + dp[j]; dp[j-1]为当前层更新后 j - 1 列（即左边）的路径数量，dp[ j ]为上一层更新的j列（即上边）路径数量

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m == 1 || n == 1) return 1;	// 一行、一列都为1
        vector dp(n+1,1);			// 下标从1开始
        for(int i = 2; i <= m; ++i){	// 第二个数开始
            for(int j = 2; j <= n; ++j){
                dp[j] = dp[j-1] + dp[j];// dp[j-1]为当前层更新后j-1列（即左边）的路径数量，dp[j]为上一层更新的j列（即上边）路径数量
            }
        }
        return dp[n];
    }
};

无论怎么走，走到终点都需要 m + n - 2 步，其中一定有 m - 1 步是要向下走的，不用管什么时候向下走。

那么有几种走法呢？ 可以转化为组合问题，即给你m + n - 2个不同的数，随便取m - 1个数，有 C ( m + n − 2 , m − 1 ) C(m+n-2, m-1) C(m+n−2,m−1)种取法。

求组合的时候，要防止两个int相乘溢出！ 所以不能把算式的分子都算出来，分母都算出来再做除法。需要在计算分子的时候，不断除以分母，代码如下：

• 时间复杂度：O(m)
• 空间复杂度：O(1)

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1; // 分子
        int denominator = m - 1; // 分母
        int count = m - 1;
        int t = m + n - 2;
        while (count--) {
            numerator *= (t--);
            while (denominator != 0 && numerator % denominator == 0) {
                numerator /= denominator;
                denominator--;
            }
        }
        return numerator;
    }
};