Java教程

动态规划

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

目录
  • 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];
    }
};
这篇关于动态规划的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!