目标:动态规划
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
兔子数列的每一项都是前两项之和,公式为f[n]=f[n−1]+f[n−2] 。 #include<bits/stdc++.h> using namespace std; int main(){ int f[105] , n; f[1] = 1; f[2] = 1; cin >> n; for(int i = 3 ; i <= n ; i++){ f[i] = f[i-1] + f[i-2]; } cout << f[n]; return 0; }View Code
[钞票问题]
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
dp[i-1] 再拿 1 张 1 元钞票,则是 i 元,因此:dp[i] = dp[i-1] + 1; dp[i-5] 再拿 1 张 5 元钞票,则是 i 元,因此:dp[i] = dp[i-5] + 1; dp[i-11] 再拿 1 张 11 元钞票,则是 i 元,因此:dp[i] = dp[i-11] + 1; 题目要求最少的组合张数,所以只需要对 dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 取最小即可。 状态转移方程:dp[i] = min{ dp[i-1]+1, dp[i-2]+1, dp[i-11]+1 }; #include<bits/stdc++.h> using namespace std; const int N = 2e6 + 10; int dp[N]; int main() { int c[5] = {1, 5, 11} , m; cin >> m ; memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= m; i++) { for (int j = 0; j < 3 ; j++){ if (i >= c[j]) { dp[i] = min((dp[i - c[j]] + 1) , dp[i]); } } } cout << dp[m] << endl; return 0; }View Code
[数字金字塔]
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
根据动态规划思想,从小的问题开始解决,我们从下往上开始计算。当前位置能获得的最大值为,当前值加上下面两数较大的值,可得动态转移方程式:dp[i][j]+=max(dp[i−1][j],dp[i−1][j+1]); #include<bits/stdc++.h> using namespace std;int dp[1005][1005]; int main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ cin >> dp[i][j]; } } for(int i = n; i >= 1; i--){ for(int j = 1; j <= i; j++){ dp[i-1][j] += max(dp[i][j] , dp[i][j+1]); } } cout << dp[1][1] << endl; return 0; }View Code
[不同的路径]
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
假设能有一种状态 dp[i][j] 表示从 (1, 1) 到达 (i, j) 不同路径的总量。那么 m*n 的网格从 (1, 1) 到达 (m, n) 不同路径的总量,就是 dp[m][n]。根据题意 dp[i][j] 作为一次阶段性终点,它只能: 从上面来:dp[i-1][j] 向下走 从左边来:dp[i][j-1] 向右走 因此: dp[i][j] = dp[i-1][j] + dp[i][j-1]; #include<bits/stdc++.h> using namespace std; const int N = 101; long long dp[N][N]; long long n, m; int main(){ cin >> m >> n; for(int i = 1; i <= m; i++) dp[i][1] = 1; for(int j = 1; j <= n; j++) dp[1][j] = 1; for(int i = 2; i <= m; i++) { for(int j = 2; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } cout << dp[m][n] << endl; return 0; }View Code
[传球游戏]
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
对于每一个同学接到球的来源可以是前一个同学,也可以是后一个同学,且还需要考虑传球次数,因此可以尝试设计状态:dp[i][j] 表示从 1 号开始传球,总共传递了 j 次,传递到 i 号的种类次数。例如 dp[1][0] 表示从 1 号开始传球传 0 次,到达 1 号。显而易见的 dp[1][0] = 1 。根据传球的来源不同,可以做如下划分: 从小编号传来:dp[i-1][j-1] 从大编号传来:dp[i+1][j-1] 因此 dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1]; #include <iostream> #include <cstring> using namespace std; typedef long long ll; ll dp[50][50]; int n, m; inline int backi(int i) { return i-1<=0? n : i-1; } inline int nexti(int i) { return i+1>n? 1 : i+1; } int main() { cin >> n >> m; dp[1][0] = 1; for (int j=1; j<=m; j++) { for (int i=1; i<=n; i++) { dp[i][j] = dp[backi(i)][j-1] + dp[nexti(i)][j-1]; } } cout << dp[1][m] << endl; return 0; }View Code
标签:11,main,05,int,U6,C++,long,include,dp From: https://www.cnblogs.com/jayxuan/p/18032871