大家好！今天想和大家分享几个简单的动态规划（Dynamic Programming, DP）算法，并且附上C++代码实现。🚀

首先，我们来聊聊什么是动态规划。简单来说，动态规划是一种通过把原问题分解为相互重叠的子问题来求解复杂问题的方法。它通常用于优化问题，比如最短路径问题或者背包问题。💡

接下来，我们看看几个经典的DP问题：

1️⃣ 斐波那契数列 🐢🐰

斐波那契数列是一个经典的递归问题，但用动态规划可以极大地提高效率。这里展示如何使用迭代方法来解决这个问题。

```cpp

int fib(int n) {

if (n <= 1) return n;

int dp[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️⃣ 最长递增子序列 📈

给定一个整数数组，找出其中最长的递增子序列。这个例子展示了如何使用动态规划来解决问题。

```cpp

int lis(vector& nums) {

int n = nums.size();

vector dp(n, 1);

for (int i = 1; i < n; i++) {

for (int j = 0; j < i; j++) {

if (nums[i] > nums[j])

dp[i] = max(dp[i], dp[j] + 1);

}

}

return max_element(dp.begin(), dp.end());

}

```

以上就是今天的分享啦！希望这些简单的例子能帮助你更好地理解动态规划的概念及其应用。如果有任何疑问或建议，欢迎留言交流！💬

编程 算法 动态规划