13、动态规划详解(入门级)

动态规划（Dynamic Programming）是一种解决复杂问题的方法，通过将问题分解为更小、更简单的子问题，并利用子问题的解来构建原问题的解。动态规划的主要特点是其能够储存并重复利用子问题的解，从而避免了重复计算。

动态规划的相关概念

状态：问题当前的描述，通常是决策过程的某个中间阶段。例如在背包问题中，状态可能包括背包的当前重量或已选取的物品。
决策：对状态的一种改变，通常对应一个或多个动作。例如在背包问题中，决策可能包括选择特定的物品。
状态转移：由当前状态和决策导致的状态改变。例如在背包问题中，选择一个物品会导致背包的重量增加。

动态规划的特点

重叠子问题：动态规划通常适用于有重叠子问题的情况，即不同的子问题包含了相同的更小的子问题。在这种情况下，动态规划可以通过只解决每个子问题一次，然后储存并重复利用子问题的解，避免了重复计算。
最优子结构：动态规划适用于具有最优子结构的问题，即问题的最优解包含了其子问题的最优解。在这种情况下，我们可以通过解决子问题并选择子问题的最优解，构建问题的最优解。

动态规划的设计步骤

描述状态：确定问题的状态，描述问题的所有可能情况。
定义状态转移方程：根据问题的规则，确定如何从一个状态转移到另一个状态。
初始化边界条件：确定初始状态和边界情况。
计算结果：通常从最简单的状态开始，按照状态转移方程计算其他状态，最后得到问题的最优解。
重构解（可选）：有时候，我们不仅需要知道问题的最优解，还需要知道如何得到最优解。这时，我们可以从最优解开始，逆向追溯到初始状态，得到解的具体构造过程。

常见的动态规划的应用案例

背包问题：这是动态规划最常见的应用之一，包括0-1背包问题、完全背包问题、多重背包问题等。背包问题涉及到如何在满足一定约束条件的前提下，最优地选择一些物品。
最长公共子序列（LCS）：给定两个序列，找出两个序列都有的最长子序列的长度。
最长递增子序列（LIS）：在给定的数值序列中，找出一个子序列，使得这个子序列是所有子序列中最长的递增序列。
矩阵链乘法：给定一系列矩阵，决定怎样的乘法顺序能够最小化总的乘法次数。
编辑距离：编辑距离用于量化两个字符串的相似程度，即将一个字符串变换成另一个字符串需要的最少操作次数（插入、删除、替换）。
最优二叉搜索树：给定一组数据和它们的访问概率，构建一棵搜索代价最小的二叉搜索树。
旅行商问题（TSP）：给定一系列城市和每对城市之间的距离，寻找访问每个城市一次并回到出发城市的最短路径。
股票买卖问题：在允许多次交易，或者限制交易次数等不同条件下，求解可以获得的最大利润。

1、斐波那契数列（简单）：斐波那契数列是一个常见的动态规划问题。斐波那契数列定义为：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)。我们可以通过动态规划的方式来优化计算过程，避免重复计算。

C++
#include<bits/stdc++.h>
using namespace std;

int fib(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

2、爬楼梯（简单）：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

C++
#include<bits/stdc++.h>
using namespace std;

int climbStairs(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << climbStairs(n) << endl;
    return 0;
}

3、最小路径和（简单）：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。注意：每次只能向下或者向右移动一步。

C++
#include<bits/stdc++.h>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];
    for(int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
    for(int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> grid(m, vector<int>(n, 0));
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    cout << minPathSum(grid) << endl;
    return 0;
}

4、背包问题（中等）：给定一组物品，每种物品都有自己的重量和价值，现在给定一个最大承重的背包，如何选择物品使得背包中物品的总价值最大，且不超过背包的最大承重。

C++
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N], dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[n][m] << endl;
    return 0;
}

5、打家劫舍（中等）：给定一个数组，代表每个房子中有的金额，你是一个专业的盗贼，打算去打劫这些房子。但是，你不能打劫相邻的两个房子，否则警报就会响起。给定一列非负整数代表每个房子的金额，确定你可以抢劫的最大金额。

C++
#include<bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums) {
    if(nums.size() == 0) return 0;
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    for(int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i-1], (i>1?dp[i-2]:0) + nums[i]);
    }
    return dp[nums.size()-1];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    cout << rob(nums) << endl;
    return 0;
}

6、零钱兑换（中等）：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

C++
#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int n, amount;
    cin >> n >> amount;
    vector<int> coins(n);
    for(int i = 0; i < n; i++) cin >> coins[i];
    cout << coinChange(coins, amount) << endl;
    return 0;
}

7、编辑距离（困难）：给定两个字符串 str1 和 str2，你需要计算出将 str1 转换成 str2 所使用的最少操作数。你可以对一个字符串进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

C++
#include<bits/stdc++.h>
using namespace std;

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++) dp[i][0] = i;
    for(int j = 1; j <= n; j++) dp[0][j] = j;
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; 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-1], dp[i-1][j], dp[i][j-1]}) + 1;
            }
        }
    }
    return dp[m][n];
}

int main() {
    string word1, word2;
    cin >> word1 >> word2;
    cout << minDistance(word1, word2) << endl;
    return 0;
}

8、最长公共子序列（较难）：给定两个字符串，找出这两个字符串的最长公共子序列。

C++
#include<bits/stdc++.h>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    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];
}

int main() {
    string text1, text2;
    cin >> text1 >> text2;
    cout << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

9、正则表达式匹配（困难）：实现一个匹配 '.' 和 '*' 的正则表达式。'.' 匹配任意单个字符，' * ' 匹配零个或多个前面的元素。

C++
#include<bits/stdc++.h>
using namespace std;

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

int main() {
    string s, p;
    cin >> s >> p;
    cout << (isMatch(s, p) ? "true" : "false") << endl;
    return 0;
}

10、最长递增子序列：设定一个dp数组，其中dp[i]代表以第i个元素结尾的最长递增子序列的长度。那么我们可以通过遍历前面的所有元素，寻找当前元素前面的比其小的元素，取其dp值最大的加1作为dp[i]。

C++
#include<bits/stdc++.h>
using namespace std;

vector<int> lengthOfLIS(vector<int>& nums) {
    if(nums.size() == 0)
        return 0;
    vector<int> dp(nums.size(), 1);
    for(int i = 1; i < nums.size(); i++){
        for(int j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) cin >> nums[i];
    vector<int> res = lengthOfLIS(nums);
    cout << *max_element(res.begin(), res.end()) << endl;
    return 0;
}

11、最优二叉搜索树的问题：假设我们有n个键（在排序顺序）和一棵二叉搜索树。键\(k_i\)的搜索频率是\(p_i\)。搜索成本一颗二叉搜索树的总成本是\(∑p_i\)*深度(\(k_i\))。我们的任务是构建一颗搜索成本最小的二叉搜索树。

C++
#include<bits/stdc++.h>
using namespace std;

int sum(int freq[], int i, int j);

int optimalSearchTree(int keys[], int freq[], int n) {
    int dp[n][n];

    for (int i = 0; i < n; i++)
        dp[i][i] = freq[i];

    for (int L = 2; L <= n; L++) {
        for (int i = 0; i <= n - L + 1; i++) {
            int j = i + L - 1;
            dp[i][j] = INT_MAX;
            for (int r = i; r <= j; r++) {
               int c = ((r > i)? dp[i][r - 1]:0) + 
                       ((r < j)? dp[r + 1][j]:0) + 
                       sum(freq, i, j);
               if (c < dp[i][j])
                  dp[i][j] = c;
            }
        }
    }
    return dp[0][n - 1];
}

int sum(int freq[], int i, int j) {
    int s = 0;
    for (int k = i; k <=j; k++)
       s += freq[k];
    return s;
}

int main() {
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys)/sizeof(keys[0]);
    cout << "Cost of Optimal BST is " << optimalSearchTree(keys, freq, n);
    return 0;
}

12、股票买卖问题简单版本：你可以尽可能多地完成交易（即买一股并卖一股），但你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

C++
#include <iostream>
#include <vector>

using namespace std;

int maxProfit(vector<int>& prices) {
    int max_profit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i-1])
            max_profit += prices[i] - prices[i-1];
    }
    return max_profit;
}

int main() {
    vector<int> prices = {7,1,5,3,6,4};
    cout << "Maximum profit: " << maxProfit(prices) << endl;
    return 0;
}

13、旅行商问题（Traveling Salesman Problem，TSP）：给定一组城市和每对城市之间的距离，找出访问每个城市一次并返回起始城市的最短路线。

C++
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
const int inf = 0x3f3f3f3f;
int dp[1 << maxn][maxn]; // dp状态数组
int dis[maxn][maxn]; // 距离矩阵

int TSP(int n) {
    // 初始化dp数组为无穷大
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = inf;
        }
    }
    dp[1][0] = 0; // 从城市0出发
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) { // 如果i状态下包含城市j
                for (int k = 0; k < n; k++) { // 遍历其他城市
                    if ((i ^ (1 << j)) >> k & 1) { // 如果除去j后的集合中包含k
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + dis[k][j]);
                    }
                }
            }
        }
    }
    int ans = inf;
    for (int i = 1; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + dis[i][0]); // 更新答案
    }
    return ans;
}

int main() {
    int n; // 城市的数量
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
                cin >> dis[i][j]; // 输入城市间的距离
        }
    }
    cout << TSP(n) << endl; // 输出最短路径长度
    return 0;
}

14、最长回文子串(Longest Palindromic Substring)问题：给定一个字符串，找到其中最长的回文子串。

C++
#include <iostream>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false)); // 初始化dp数组
    int maxLength = 0;
    int start = 0;

    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        if (maxLength < 1) {
            maxLength = 1;
            start = i;
        }
        if (i < n - 1 && s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            if (maxLength < 2) {
                maxLength = 2;
                start = i;
            }
        }
    }

    for (int length = 3; length <= n; ++length) {
        for (int i = 0; i < n - length + 1; ++i) {
            int j = i + length - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (maxLength < length) {
                    maxLength = length;
                    start = i;
                }
            }
        }
    }

    return s.substr(start, maxLength);
}

int main() {
    string s = "babad";
    string longestPalindromicSubstr = longestPalindrome(s);
    cout << "最长回文子串：" << longestPalindromicSubstr << endl;
    return 0;
}

15、最大正方形（Maximal Square）问题：给定一个二维的 0-1 矩阵，找出全为 1 的最大正方形，并返回其面积。

C++
#include <iostream>
#include <vector>
using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始化dp数组
    int maxSide = 0;

    for (int i = 0; i < m; ++i) {
        dp[i][0] = matrix[i][0] - '0';
        maxSide = max(maxSide, dp[i][0]);
    }
    for (int j = 0; j < n; ++j) {
        dp[0][j] = matrix[0][j] - '0';
        maxSide = max(maxSide, dp[0][j]);
    }

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == '1') {
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

int main() {
    vector<vector<char>> matrix = {
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'}
    };
    int maxSquareArea = maximalSquare(matrix);
    cout << "最大正方形的面积：" << maxSquareArea << endl;
    return 0;
}

16、单词拆分（Word Break）问题：给定一个非空字符串s和一个包含非空单词列表的字典wordDict，在字符串中添加空格来构建一个句子，使得句子中的每个单词都是字典中的单词。返回所有可能的句子组成的列表。

C++
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<string> wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.length();
    vector<vector<string>> dp(n + 1); // 初始化dp数组

    dp[0] = {""};

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            string word = s.substr(j, i - j);
            if (dict.count(word) && !dp[j].empty()) {
                for (string prevWord : dp[j]) {
                    dp[i].push_back(prevWord + (prevWord.empty() ? "" : " ") + word);
                }
            }
        }
    }

    return dp[n];
}

int main() {
    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    vector<string> sentences = wordBreak(s, wordDict);

    cout << "所有可能的句子：" << endl;
        for (string sentence : sentences) {
        cout << sentence << endl;
    }

    return 0;
} 

17、最大子数组和（Maximum Subarray Sum）问题：给定一个整数数组，找到一个具有最大和的连续子数组，返回其最大和。

C++
#include <iostream>
#include <vector>
using namespace std;

int maxSubarraySum(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0); // 初始化dp数组
    int maxSum = nums[0];

    dp[0] = nums[0];

    for (int i = 1; i < n; ++i) {
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = maxSubarraySum(nums);
    cout << "最大子数组和：" << maxSum << endl;
    return 0;
}

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用