LeetCode刷题之DP算法

2021/11/29 11:36:49

本文主要是介绍LeetCode刷题之DP算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LeetCode刷题之动态规划算法

1.基本思路及代码框架

首先,动态规划的穷举有点特别,因为这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算。

而且,动态规划问题一定会具备「最优子结构」,才能通过子问题的最值得到原问题的最值。

另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」,才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解,但是在实际的算法问题中,写出状态转移方程是最困难的,这也就是为什么很多朋友觉得动态规划问题困难的原因,我来提供我研究出来的一个思维框架,辅助你思考状态转移方程:

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

按上面的套路走,最后的结果就可以套这个框架:

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 求最值(选择1,选择2...)

2.题目解答

1.LeetCode之509斐波拉且数列

  • 解题思路

    • 第一种,采用递归思想,直接写出递归函数
    • 第二种,记录下每种情况,避免重复计算。
  • 代码实现

    1.递归方程

    /*
     * @lc app=leetcode.cn id=509 lang=cpp
     *
     * [509] 斐波那契数
     */
    
    // @lc code=start
    class Solution {
    public:
        int fib(int n) {
            if (n == 0) return 0;
            if (n == 1 || n == 2) {
                return 1;
            }
            return fib(n -1) + fib(n - 2);
        }
    };
    // @lc code=end
    

    2.子状态记录

    class Solution {
    public:
        int fib(int n) {
            if (n == 0) {
                return 0;
            }
            int *dp = new int[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];
        }
    };
    

2.LeetCode之322零钱兑换

  • 解题思路

    采用动态规划求解,避免递归。找出基础状态,选择,以及目标。写出状态方程:

    img

  • 代码实现

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            vector<int> dp(amount + 1,amount + 1);
    
            dp[0] = 0;
            for (int i = 0; i < dp.size(); i++) {
                for (auto coin : coins) {
                    if (i - coin < 0) {
                        continue;
                    }
                    dp[i] = min(dp[i], 1 + dp[i - coin]);
                }
            }
            return (dp[amount] == amount + 1) ? -1 : dp[amount];
        }
    };
    

3.LeetCode之300最长递增子序列

  • 解题思路

    状态转移方程:我们以dp[i]表示以num[i]结尾得最长递增子序列的长度。

    根据这个定义,我们的最终结果(子序列的最大长度)应该是 dp 数组中的最大值。

    int res = 0;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
    

    nums[5] = 3,既然是递增子序列,我们只要找到前面那些结尾比 3 小的子序列,然后把 3 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一

    显然,可能形成很多种新的子序列,但是我们只选择最长的那一个,把最长子序列的长度作为 dp[5] 的值即可。

    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) 
                dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    
  • 代码实现

    /*
     * @lc app=leetcode.cn id=300 lang=cpp
     *
     * [300] 最长递增子序列
     */
    
    // @lc code=start
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            vector<int> dp(nums.size(), 1);
    
            for (int i = 0; i < nums.size(); i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            int res = 0;
            for(int i = 0; i < nums.size(); i++) {
                res = max(res, dp[i]);
            }
    
            return res;
        }
    };
    // @lc code=end
    

4.LeetCode之1143最长公共子序列

  • 解题思路

    明确基础状态,写出状态,做出选择。

    写出状态方程。img

  • 代码实现

    /*
     * @lc app=leetcode.cn id=1143 lang=cpp
     *
     * [1143] 最长公共子序列
     */
    
    // @lc code=start
    class Solution {
    public:
        int longestCommonSubsequence(string text1, string text2) {
            int m = text1.size(), n = text2.size();
            vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (text1[i - 1] == text2[j - 1]) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[m][n];
        }
    };
    // @lc code=end
    

5.LeetCode之583两个字符串的删除操作

  • 解题思路

    与上一题解法思路一致,只不过最终结果需要转化一下。

  • 代码实现

    /*
     * @lc app=leetcode.cn id=583 lang=cpp
     *
     * [583] 两个字符串的删除操作
     */
    
    // @lc code=start
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m =word1.size(), n =word2.size();
            vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (word1[i - 1] ==word2[j - 1]) {
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return m + n - 2 * dp[m][n];
        }
    };
    // @lc code=end
    

6.LeetCode之712两个字符串的最小ASCII删除和

  • 解题思路

    先给出基本状态,明确数组的含义,初始化数组,给出状态,做选择。

  • 代码实现

    /*
     * @lc app=leetcode.cn id=712 lang=cpp
     *
     * [712] 两个字符串的最小ASCII删除和
     */
    
    // @lc code=start
    class Solution {
    public:
    
        int minimumDeleteSum(string s1, string s2) {
            int m = s1.size(), n = s2.size();
            vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
            for (int i = m - 1; i >= 0; i--) {
                dp[i][n] = dp[i + 1][n] + s1[i];
            }
    
            for (int j = n - 1; j >= 0; j--) {
                dp[m][j] = dp[m][j + 1] + s2[j];
            }
    
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n -1; j >= 0; j--) {
                    if (s1[i] == s2[j]) {
                        dp[i][j] = dp[i + 1][j + 1];
                    } else {
                        dp[i][j] = min(dp[i + 1][j] + s1[i],
                        dp[i][j + 1] + s2[j]);
                    }
                }
            }
            return dp[0][0];
        }
    
    };
    // @lc code=end
    


这篇关于LeetCode刷题之DP算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程