动态规划

本文主要是介绍动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• JS10 斐波那契数列
• JS10 青蛙跳台阶问题
• JO27 字符串的排列（超级经典!!!!!字符串+动态规划）
• JS14 JO67 剪绳子I（动态规划）
• JS14 剪绳子II（未写）
• L121 买卖股票的最佳时机I（!!!!!字节常考）
• L122 买卖股票的最佳时机II（字节常考）
• L123 买卖股票的最佳时机III（未写）
• L198 打家劫舍I：线形房（字节常考）
• L213 打家劫舍II：环形房
• L337 打家劫舍III：树形房（后序遍历）
• JS19 正则表达式匹配
• JS42 连续子数组的最大和
• L72 编辑距离
• L62 不同路径1
• L63 不同路径2

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

对于刷题来说，只要知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，就够用了。

动态规划5步：

• 确定dp数组（dp table）以及下标的含义

• 确定递推公式

• dp数组如何初始化

• 确定遍历顺序

• 举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的

JS10 斐波那契数列

class Solution {
public:
// dp数组的迭代解法：循环迭代+状态转移表dp（当前状态与所有状态有关）/ 状态压缩（当前状态只与部分状态有关）（自底向下），状态体现在数组索引
// 当前状态只与之前的两个状态有关
/*
    int fib(int n) {
        if(n==0||n==1)return n;
        int a = 0, b=1, sum =0;
        for(int i=2; i<=n; ++i){
            sum = (a+b) % 1000000007;
            a=b;
            b=sum;
        }
        return sum;
    }
*/
// 记忆化递归：递归+备忘录（自顶向下） dp函数：状态体现在函数参数上
    int fib(int n){
        if(n==0) return 0;
        // 将备忘录初始化为0
        vector<int> memo(n+1,0);
        // 进行带备忘录的递归
        return dp(memo,n);
    }
    int dp(vector<int>& memo, int n){
        if(n==1 || n==2) return 1;
        // 判断是否已经计算过
        if(memo[n] !=0) return memo[n];
        memo[n] = (dp(memo,n-1) + dp(memo, n-2)) % 1000000007;
        return memo[n];
    }
};

JS10 青蛙跳台阶问题

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[2]+dp[1];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};


class Solution {
public:
    int numWays(int n) {
        if(n==0 || n==1) return 1;
        int a = 1, b=1, sum =0;
        for(int i=2; i<=n; ++i){
            sum = (a+b) % 1000000007;
            a=b;
            b=sum;
        }
        return sum;
    }
};

JO27 字符串的排列（超级经典!!!!!字符串+动态规划）

JS14 JO67 剪绳子I（动态规划）

• 数学规律法

class Solution {
public:
    // 大于2和3的数都可以由2和3相加可得
    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;

        int x = n % 3, y = n / 3;
        if(x == 0) return pow(3, y);
        else if(x == 1) return 2 * 2 * pow(3, y - 1);
        else return 2 * pow(3, y);
    }
};

• 动态规划法
  讲解视频

class Solution {
public:
    // 大于2和3的数都可以由2和3相加可得
    int cuttingRope(int n) {
        if(n == 2 || n == 3) return n - 1;
        vector<int> dp(n+1, 0);
        dp[0] = dp[1] = 1;

        for(int i = 2; i <= n; ++i){
            dp[i] = i-1;  // 初始剪成1和n-1长度，即分为2 段：1 * （i-1）
            for(int j = 2; j < i; ++j){
                // 剪成j和i-j长度
                // i-j可以继续往下剪，而结果dp[i-j]已知
                dp[i] = max(dp[i], dp[i-j] * j);
                // i-j不继续往下剪，即就剪成成两段
                dp[i] = max(dp[i], (i-j) * j);
            }
        }
        return dp[n];
    }
};

JS14 剪绳子II（未写）

L121 买卖股票的最佳时机I（!!!!!字节常考）

只能买卖一次（这类题目贪心算法更好解决），从1开始遍历

• 贪心解法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 贪心算法解决
        // 因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
        int low = INT_MAX;
        int result = 0;
        for(int i=0; i<prices.size(); ++i){
            // 当天价格卖出
            low = min(low, prices[i]);  // 取左边最小价格作为买入
            result = max(result, prices[i]-low);  // 直接取最大区间利润
        }
        return result;
    }
};

• 动态规划解法：

class Solution {
public:
/*
动态规划
dp[i][0] 表示第i天持有股票所得现金
dp[i][1] 表示第i天不持有股票所得现金
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
    第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
    第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i])
——持有股票是还没有赚钱的，此时的拥有的现金是负数的，即买股票出的钱
——dp[i][0]取今天买股票花的钱和之前买股票花的钱的最小值，取负即为最大值
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
    第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
    第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]
同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
——不持有股票表示股票已经卖出去了，赚钱了
——dp[i][1]取在今天卖出股票赚到的钱和在之前卖出股票赚到的钱的最大值
dp数组如何初始化
由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出
其基础都是要从dp[0][0]和dp[0][1]推导出来。
那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。
*/
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2));
        // dp[i][0] 表示第i天持有股票所得现金
        // dp[i][1] 表示第i天不持有股票所得最多现金

        // 初始化
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        // 从第2天开始遍历
        for(int i=1; i < len; ++i){

            // 第i天持有股票所得现金(第i天及之前花出去的钱的最大值)
            // 取今天买股票和之前买股票花的钱的最小值，取负即最大值
            dp[i][0] = max(-prices[i], dp[i-1][0]);

            // 第i天不持有股票所得现金
            // 取今天才卖股票和之前卖股票赚的钱的最大值
            dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1]);

        }
        return dp[len-1][1];
    }
};

L122 买卖股票的最佳时机II（字节常考）

可以买卖多次，从1开始遍历

• 贪心算法：

#include<iostream>
#include<vector>
using namespace std;
int maxProfit(vector<int>& prices){
    int result = 0;
    for(int i = 1; i< prices.size(); ++i){
        result += max(prices[i] - prices[i-1], 0);
    }
    return result;
}
int main(){
    vector<int> prices{7, 1, 5, 3, 6, 4};
    int result = maxProfit(prices);
    cout << result<< endl;
    return 0;
}

• 动态规划：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp[i][0] 表示第i天持有股票所得现金
        // dp[i][1] 表示第i天不持有股票所得最多现金
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < len; i++) {
            // 第i天持股票所剩的最多现金 = max(第i-1天持股票所剩现金, 第i-1天不持有股票所剩现金-买第i天的股票)
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 第i天不持有股票所剩的最多现金 = max(第i-1天不持有股票所剩现金，第i-1天持有股票所剩现金+第i天卖出股票)
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return max(dp[len - 1][0], dp[len - 1][1]);
    }
};

L123 买卖股票的最佳时机III（未写）

可以买卖两次，从1开始遍历

L198 打家劫舍I：线形房（字节常考）

class Solution {
public:
    int rob(vector<int>& nums) {
        // (1)dp[i]:考虑下标i（包括i以内）的房屋，最多可以偷窃的金额为dp[i];
        // (2)确定递推公式：看第i间房偷不偷（偷第i间房：dp[i] = nums[i]+dp[i-2];第i间房不偷：dp[i] = dp[i-1]），看这2种方案哪个钱多
        // dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        // (3)dp数组初始化：递推公式的基础就是dp[0]和dp[1]
        // dp[0]=nums[0];dp[1]=max(nums[0],nums[1])
        // （4）遍历顺序：dp[i]是根据dp[i-2]和dp[i-1]推导出来的，一定是从前往后遍历
        // 先处理特殊情况
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        // 创建dp数组
        vector<int> dp(nums.size());
        // dp数组初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        // 从前往后遍历
        for(int i=2; i<nums.size(); ++i){
            // 状态转移公式/递推公式
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[nums.size()-1];
    }
};

L213 打家劫舍II：环形房

class Solution {
public:
    int rob(vector<int>& nums) {
        // 由于数组成环，考虑两种情况：考虑包含首元素，不包含尾元素；考虑包含尾元素。不包含首元素。——对这两种情况进行打家劫舍I
        // 将打家劫舍I的代码独立开来，再将这两种情况的数组传进去，最终结果就是这两个返回结果的最大值
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        int result1 = robBase(nums, 0, nums.size()-2);  // 情况1
        int result2 = robBase(nums, 1, nums.size()-1);  // 情况2
        return max(result1, result2);
    
    }
    int robBase(vector<int>& nums, int start, int end){
        if(start==end) return nums[start];
        // 创建dp数组
        vector<int> dp(nums.size());
        // 初始化
        dp[start] = nums[start];
        dp[start+1] = max(nums[start],nums[start+1]);
        // 遍历
        for(int i=start+2; i<=end; i++){
            dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
        }
        return dp[end];
    }
};

L337 打家劫舍III：树形房（后序遍历）

关键是要讨论当前节点抢还是不抢。

如果抢了当前节点，两个孩子就不是动，如果没抢当前节点，就可以考虑抢左右孩子

dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

所以本题dp数组就是一个长度为2的数组！也是函数返回值

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }

    // 长度为0的数组，0：不偷；1：考虑偷
    vector<int> robTree(TreeNode* cur){

	// 遇到叶子节点无论偷还是不偷都是0，所以就返回
        if(cur == NULL) return vector<int> {0,0};

        // 后序遍历，因为计算当前节点的dp需要左右子节点的dp
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);

        // 当前节点偷(左右子节点就不能偷)
        int val1 = cur->val + left[0] + right[0];
        // 不偷当前节点(左右子节点可偷可不偷)
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

JS19 正则表达式匹配

参考他人思路：

• 方法1：暴力递归，超出时间限制

/*
如果模式的下一个字符为'*'，则分成两个情况：如果当前字符匹配，则字符串向后移动一位或者模式向后移动2位；反之，如果当前字符不匹配，则模式向后移动2位。
如果模式的下一个字符不是'*'，如果当前字符匹配或者模式为'.'，则继续匹配下一个字符，否则返回false
*/
// 模式串p，字符串s
    bool isMatch(string s, string p) {
        // 条件只需判断模式串是否为0，不用判断字符串长度是否为0（长度为0也可以用模式串匹配）
        if(p.empty()){
            return s.empty();
        }
        return match(s, p, 0, 0);
    }
private:
    // 后两个参数为字符串和模式串的当前字符坐标
    bool match(string s, string p, int i, int j){
         // 字符串和模式串都运行到了结尾，返回true
        if(i == s.size() && j==p.size()) return true;
        
        // 字符串没有到结尾，模式串到了，则返回false——p已经到最后，但是s还没有匹配结束，则匹配失败
        // 模式串没有到结尾，字符串到了，则根据后续判断进行，需要对'*'做处理
        if(i != s.size() && j==p.size()) return false;
        // 如果模式的下一个字符为'*'，则进入状态机的匹配,分成两个情况：
        // (1)如果当前字符匹配，则字符串向后移动一位或者模式向后移动2位；
        // (2)反之，如果当前字符不匹配，则模式向后移动2位。
        if(p[j+1] == '*'){
            // 如果字符串和模式串当前字符相等，或者模式串当前字符是'.'，并且字符串没有到结尾，则继续匹配
            if(s[i]==p[j] || (i < s.size() && p[j] == '.'))
                // *匹配0次结束、匹配1次结束、继续匹配多次
                return match(s, p, i, j+2) || match(s, p, i+1, j+2) || match(s, p, i+1, j);
            // 当前字符不匹配，即*匹配0次
            else 
                return match(s, p, i, j+2);
        }
        // 如果模式的下一个字符不是'*'：如果当前字符匹配或者模式为'.'，则继续匹配下一个字符，否则返回false。
        else{
            if(s[i]==p[j] || (i < s.size() && p[j] == '.'))
                return match(s, p, i+1, j+1);
            else
                return false;
        }

    }
};

• 方法2：动态规划

class Solution {
public:
/*
定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match
本题的dp数组的含义就是：dp[i][j]就是s的前i个元素是否可以被p的前j个元素所匹配。
我们知道了dp数组的含义之后就知道了dp数组的几个细节：
1.dp[0][0]一定是true，因为s为空且p也为空的时候一定是匹配的；
2.dp[1][0]一定是false，因为s有一个字符但是p为空的时候一定是不匹配的。
3.这个boolean类型的dp数组的大小应该是dp[s.length+1][p.length+1]，因为我们不仅仅要分别取出s和p的所有元素，还要表示分别取s和p的0个元素时候(都为空)的情况。
4.当写到dp[s.length][p.length]的时候，我们就得到了最终s和p的匹配情况。
5.dp[1][0]~dp[s.length][0]这一列都是false，因为s不为空但是p为空一定不能匹配。
6.所以创建好dp数组之后，初始化dp[0][0]=true、dp[0][1]=false、dp[1][0]~dp[s.length][0]都是false。然后将第一行即dp[0][2]到dp[0][p.length]的元素初始化。
7.第一行初始化思路：如果不为空的p想要匹配上为空的s，因为此时p已经不为空，则需要p是"a*"、"b*"、"c*"。。。这种形式的才能匹配上。
8.然后填写数组的其余部分，这个过程中如果p.charAt(j)=='*'依然是遵循上题中的两种情况；否则就判断两个字符串的i和j号字符是否相等，相等则分别减除当前字符继续判断，不相等则直接等于false。
*/
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1; // 加上为空的情况
        
        //dp[i][j]表示s的0到i-1和p的0到j-1是否匹配
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        //  需要注意，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。
        /*
        初始化： 需要先初始化 dp 矩阵首行，以避免状态转移时索引越界。
        dp[0][0] = true： 代表两个空字符串能够匹配。
        dp[0][1]:如果不为空的p想要匹配上为空的s，因为此时p已经不为空，则需要p是"a*"、"b*"、"c*"。。。这种形式的才能匹配上。
        dp[1][0]~dp[s.length][0]：s不为空但是p为空一定不能匹配
        但dp[0][1]和dp[1][0]~dp[s.length][0]默认值为false所以不需要显式初始化
        dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*'： 首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）。因此，循环遍历字符串 p ，步长为 2（即只看偶数位）。
        */
        // p为空，s为空，匹配
        dp[0][0] = true;
        
        // s为空，用不为空的p匹配
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        /*
        转移方程： 需要注意，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。
        当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
            dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配；
            dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
            dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配；
        当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
            dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
            dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 1] 时，能否匹配；
        */
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                // p[j - 1] 是模式串的当前字符，dp[i][j]表示s的0到i-1和p的0到j-1是否匹配
                // 分开讨论模式串当前字符为* 和不用*情况
                // 模式串当前字符为*，对于字符组合 p[j - 2] *
                // 更好的理解方式是用字符串当前字符去与模式串*前面的字符比较，只看成功匹配情况：
                // 1当p[j-1]为*时：当前状态=比较s[i-1]与p[j - 2]* + 结合以前状态
                    // 1）当前状态：s[i-1]与p[j-2]不匹配（p[j - 2] *直接消失） + 以前状态：s[i-1]和p[j-3]之前所有字符匹配情况——dp[i-1][j-2]
                    // 2) 当前状态：s[i-1]与p[j-2]字符匹配或p[j-2]为'.'（p[j-2]*匹配了一次，之前状态可能有多次p[j-2]*的匹配）+ 以前状态：s[i-2]与p[j-2]*的之前所有字符的匹配情况——dp[i-1][j]
                // 2当p[j-1]不为*时：当前状态=比较s[i-1]]与p[j-1] + 结合以前状态dp[i-1][j-1]
                dp[i][j] = p[j - 1] == '*' ?
                    // 当前字符串s[i-1]不匹配（*可以匹配0次，即p[j - 2] *直接消失）,只需看s[i-1]和p[i-3]匹配情况；
                    // 当前字符串s[i-1]与p[j-2]*匹配1次或者p[j-2]为'.'
                    dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):
                    dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

• 无注释版本

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = p[j - 1] == '*' ?
                    dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):
                    dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

JS42 连续子数组的最大和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //(2)最长递增子序列：动态规划
        // 动态规划：（自底向上）循环迭代+状态转移表
        // 1）明确数组dp含义：dp[i]表示以nums[i]这个数为结尾的最大连续子数组和
        // 2）运用数学归纳思想：假设dp[0]...dp[i-1]已知，推导出dp[i]
        //   dp[i]有两种选择，要么与前面的相邻子数组连接形成一个更大的子数组，要么自己一个人作为子数组
        //   求dp[i]：dp[i]只与dp[i-1]有关，dp[i-1]已知，则dp[i]为max(num[i],num[i]+dp[i-1]),即如果nums[i]与前面数组连接后的与自己不连接单独一人作比较
        // 3）dp数组的最大值为所求
        int length = nums.size();
        if (length==0) return 0;
        // base case
        // 第一个数组前面没有子数组
        int dp_0 = nums[0];
        int dp_1 = 0;
        int maxSum = dp_0;
        for (int i=1; i<length; ++i){
            dp_1 = max(nums[i], nums[i]+dp_0);
            dp_0 = dp_1;
            maxSum = max(maxSum, dp_1);
        }
        return maxSum;
    }
};

L72 编辑距离

class Solution {
public:
/*
1 确定dp数组（dp table）以及下标的含义
    dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
2 确定递推公式
*/
    int minDistance(string word1, string word2) {
        // 定义dp数组
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        // 初始化dp数组
        for(int i = 0; i <= word1.size(); ++i) dp[i][0] = i;
        for(int j = 0; j <= word2.size(); ++j) dp[0][j] = j;
        // 遍历
        for(int i = 1; i <= word1.size(); ++i){
            for(int j = 1; j <= word2.size(); ++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{  // 当两个数组对应元素不等时，分别采取增、删、替换等操作找最小编辑距离
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

L62 不同路径1

class Solution {
public:
/*
机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
1、确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2、确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] =  dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
3、dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
4、确定遍历顺序
这里要看一下递归公式dp[i][j] =  dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
5、举例推导dp数组
*/
    int uniquePaths(int m, int n) {
        // 确定dp数组及下标含义：dp[i][j] 表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // dp数组初始化
        for(int i=0; i<m; i++) dp[i][0]=1;
        for(int j=0; j<n; j++) dp[0][j]=1;
        // 遍历进行状态转移，从坐标[1,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];

    }
};

L63 不同路径2

有路障，只要考虑到，遇到障碍dp[i][j]保持0就可以了

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        // dp数组创建
        vector<vector<int>> dp(m, vector<int>(n,0));
        // dp数组初始化:如果遇到路障，后面都不能走了
        for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0]=1;
        for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j]=1;
        // 遍历进行状态转移,从坐标[1,1]开始
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                // 一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作
                if(obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i-1][j] +dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

这篇关于动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！