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;
}