05.01 动态规划基础

1. 把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。
2. 在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。

动态规划与分治算法的不同点在于：

1. 适用于动态规划求解的问题，在分解之后得到的子问题往往是相互联系的，会出现若干个重叠子问题。
2. 使用动态规划方法会将这些重叠子问题的解保存到表格里，供随后的计算查询使用，从而避免大量的重复计算。

不同路径

分析

1. 划分阶段：按照路径的结尾位置（行位置、列位置组成的二维坐标）进行阶段划分。
2. 定义状态：dp[i][j]表示到达坐标(i,j)位置有多少条不同的路径。
3. 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
4. 初始条件和边界条件：初始dp[0][0] = 1；边界条件，当i = 0时，dp[0][j] = 1，即只能由向右走得到；当j = 0时，dp[i][0] = 1，即只能由向下走得到。
5. 最终结果：返回dp[m-1][n-1]。

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 定义状态数组
        vector<vector<int>> dp(m, vector<int>(n));
        // 填充行,dp[0][j] = 1
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        // 填充列
        for(int i = 0; i < m; i++){
            dp[i][0] = 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(n^2)$
• 空间复杂度：O(1)

记忆化搜索是动态规划的一种实现方式。在记忆化搜索中，当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。

• 记忆化搜索：「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。

优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。

缺点：可能会因为递归深度过大而导致栈溢出问题。

• 递推：「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。

优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。

缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。

适合使用「记忆化搜索」的场景：

• 问题的状态转移方程比较复杂，递推关系不是很明确。

• 问题适合转换为递归形式，并且递归深度不会太深

适合使用「递推」的场景：

• 问题的状态转移方程比较简单，递归关系比较明确。

• 问题不太适合转换为递归形式，或者递归深度过大容易导致栈溢出。

1. 写出问题的动态规划「状态」和「状态转移方程」。
2. 定义一个缓存（数组或哈希表），用于保存子问题的解。
3. 定义一个递归函数，用于解决问题。在递归函数中，首先检查缓存中是否已经存在需要计算的结果，如果存在则直接返回结果，否则进行计算，并将结果存储到缓存中，再返回结果。
4. 在主函数中，调用递归函数并返回结果。

目标和

分析

class Solution {
public:
    // 定义一个哈希表，存储索引和当前和
    unordered_map<string, int> hash;  // 使用字符串作为键
    int findTargetSumWays(vector<int>& nums, int target) {
        return dfs(nums, target, 0, 0);
    }
    int dfs(vector<int>& nums, int target, int index, int curSum) {
        // 如果是最后一个数字
        if (index == nums.size()) {
            // 如果等于目标
            return curSum == target ? 1 : 0;
        }
        
        // 记忆化搜索，使用字符串作为哈希表的键
        string key = to_string(index) + "," + to_string(curSum);
        if (hash.find(key) != hash.end()) {
            return hash[key];
        }
        
        // 搜索下一个
        int cnt = dfs(nums, target, index + 1, curSum - nums[index]) + 
                  dfs(nums, target, index + 1, curSum + nums[index]);
        hash[key] = cnt;  // 存储结果
        return cnt;
    }
};

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(n)$。递归调用的栈空间深度不超过n。

猜数字大小II

分析

通过二分查找方法，能够找到猜中的最小次数，但这个猜中的最小次数所对应的支付金额，并不是最小现金数。

$f(1)(n) = min_{x = 1}^{x = n} \lbrace max \lbrace f(1)(x - 1), f(x + 1)(n) \rbrace + x \rbrace$

class Solution {
public:
    int getMoneyAmount(int n) {
        // 定义状态数组
        vector<vector<int>> dp(n+2, vector<int>(n+2));
        // 枚举区间长度
        for(int len = 2; len <= n; len++){
            // 左端点
            for(int i = 1; i <= n; i++){
                int j = i + len - 1;    // 右端点
                if(j > n){  // 超出数字范围
                    break;
                }
                // 枚举区间内数字
                dp[i][j] = INT_MAX;
                for(int k = i; k <= j; k++){
                    dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j])+k);
                }
            }
        }
        return dp[1][n];
    }
};

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$