LeetCode刷题之DP算法

2022-09-30 21:43:59

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零钱兑换

解题思路

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

代码实现

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最长公共子序列

解题思路

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

写出状态方程。

代码实现

/*
 * @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刷题之动态规划算法

1.基本思路及代码框架

2.题目解答

1.LeetCode之509斐波拉且数列

2.LeetCode之322零钱兑换

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

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

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

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

相关文章