这篇文章上次修改于 754 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

1 题目特点

1.1 计数

  • 有多少种方式走到右下角
  • 有多少种方法选出 k 个数字使得和是 Sum

1.2 求最大最小值

  • 从左上角到右下角路径的最大数字和
  • 最长上升子序列长度

1.3 求存在性

  • 取石子游戏，先手是否必胜
  • 能不能选出 k 个数字使得和是 Sum

2 思路

  1. 确定状态

    • 最后一步
    • 化成子问题

  2. 转移方程

    • 根据子问题定义直接得到

  3. 初始条件和边界情况

    • 细心，考虑周全

  4. 计算顺序

    • 利用之前的计算结果

  5. 消除冗余，加速计算

    • 滚动数组

3 入门题

3.1 Coin Change

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

Example1
Input:
[1, 2, 5]
11
Output: 3
Explanation: 11 = 5 + 5 + 1

class Solution {
public:
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                int res_amount = i - coins[j];
                if (res_amount >= 0 && dp[res_amount] != INT_MAX && dp[res_amount] + 1 < dp[i]) {
                    dp[i] = dp[res_amount] + 1;
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

3.2 不同路径

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

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

3.3 跳跃游戏

给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。

class Solution {
public:
    /**
     * @param a: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &a) {
        int n = a.size();
        vector<bool> dp(n, false);
        dp[0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + a[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }
};

如果用贪心的话可以达到 O(n)。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int right_most = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i <= right_most) {
                right_most = max(right_most, i + nums[i]);
                if (right_most >= nums.size() - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

4 常见动态规划类型

  • 坐标型动态规划
  • 序列型动态规划
  • 划分型动态规划
  • 区间型动态规划
  • 背包型动态规划
  • 最长序列型动态规划
  • 博弈型动态规划
  • 综合性动态规划

参考

动态规划DP算法. https://www.bilibili.com/video/BV1nt4y1Y7n7?spm_id_from=333.999.0.0