c++动态规划之动态转移方程
动态规划(Dynamic Programming)是一种解决优化问题的方法,它通过将问题分解成子问题,然后将子问题的解存储起来,以便后续的计算中重复利用,从而降低计算复杂度。动态规划的核心是动态转移方程,它描述了问题的子问题之间的转移关系,是动态规划算法的关键之一。
在C++中,动态规划的动态转移方程通常通过递推关系来描述。以解决最长递增子序列(Longest Increasing Subsequence)问题为例,动态转移方程可以描述为:
// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
// dp[i] = max(dp[j] + 1), 0 <= j < i 且 nums[j] < nums[i]
int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}vector<int> dp(n, 1);int maxLen = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}return maxLen;
}
在上面的例子中,动态转移方程 dp[i] = max(dp[j] + 1), 0 <= j < i 且 nums[j] < nums[i] 表示了以 nums[i] 结尾的最长递增子序列的长度。通过这个动态转移方程,我们可以递推计算得到最终的解。在实际的动态规划问题中,动态转移方程的描述可以是不同的,但它通常是问题的核心,通过它我们可以将问题分解成子问题,从而得到问题的最优解。
那么,如何寻找动态转移方程也成为了动态规划一大难题
寻找动态转移方程是动态规划问题的关键步骤,下面是一些常用的方法和技巧来寻找动态转移方程:
1. 确定问题的状态:动态规划问题通常涉及一些状态的转移,因此首先需要确定问题的状态是什么。状态是问题的关键信息,它可以是一个或多个变量的取值,可以是一个数组或矩阵的元素,或者是一些其他的信息。确定问题的状态可以帮助我们找到问题的子问题和状态转移关系。
2. 定义状态的含义:确定问题的状态后,需要定义状态的含义,即状态变量的取值代表什么含义。状态的含义通常是问题的一些关键信息,例如最长递增子序列的长度,最大子数组的和,最短编辑距离等等。
3. 确定状态转移方程:状态转移方程描述了问题的子问题之间的转移关系。它通常是一个递推关系,即通过已知的子问题的解来推导出当前问题的解。可以通过观察问题的特点和已知的子问题的解来寻找状态转移方程。常见的方法包括:找出当前状态和之前状态之间的关系,找出当前状态和之前状态的最优解之间的关系,或者通过已知的子问题的解来推导出当前问题的解。
4. 确定初始条件和边界条件:动态规划问题通常需要确定一些初始条件和边界条件,用来定义问题的边界和初始状态。初始条件是最小规模的子问题的解,边界条件是问题的边界情况下的解。初始条件和边界条件可以帮助我们递推计算出问题的最优解。
通过以上的方法和技巧,可以帮助我们寻找动态转移方程,解决动态规划问题。需要注意的是,寻找动态转移方程是一个需要经验和技巧的过程,需要多多练习和思考。
练习题
硬币问题 - 洛谷
# 硬币问题
## 题目描述
今有面值为 1、5、11 元的硬币各无限枚。
想要凑出 $n$ 元,问需要的最少硬币数量。
## 输入格式
仅一行,一个正整数 $n$。
## 输出格式
仅一行,一个正整数,表示需要的硬币个数。
## 样例 #1
### 样例输入 #1
```
15
```
### 样例输出 #1
```
3
```
## 样例 #2
### 样例输入 #2
```
12
```
### 样例输出 #2
```
2
```
## 提示
#### 样例解释
对于样例数据 1,最佳方案是 $15=5+5+5$,使用到 3 枚硬币。
对于样例数据 2,最佳方案是 $12=11 + 1$,使用到 2 枚硬币。
#### 数据规模与约定
对于 $100\%$ 的数据,保证 $n\leq 10^6$。
此题动态转移方程为f[i]=min(f[i],f[i-1]+1,f[i-5]+1,f[i-11]+1);
完整代码
#include <bits/stdc++.h>
using namespace std;
int main() {int n,f[99999];cin>>n;f[0]=0;f[1]=1;for(int i=2;i<=100;i++){int mn=99999;if(i-1>=0)mn=min(mn,f[i-1]+1);if(i-5>=0)mn=min(mn,f[i-5]+1);if(i-11>=0)mn=min(mn,f[i-11]+1);f[i]=mn;//cout<<f[i]<<endl;}cout<<f[n];return 0;
}