动态规划(高数Umaru系列9——哈士奇、最少硬币问题、数字三角形问题、最长公共子序列问题、石子合并问题)

本文主要是介绍动态规划(高数Umaru系列9——哈士奇、最少硬币问题、数字三角形问题、最长公共子序列问题、石子合并问题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.高数Umaru系列9——哈士奇

题目描述：
由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有X元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱X以及N条哈士奇的价格和萌值，求高数巨最多可获得多少萌值

输入格式：
多组输入。

对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数

接下来的N行每行有两个整数Pi，Mi（1 < = Pi,Mi < = 100），分别表示第i条哈士奇的价格和萌值

输出格式：
对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行

样例
输入：

输出：

40
95
0

思路：
此题为经典的01背包问题

代码一：(二维DP）

#include<bits/stdtr1c++.h>
using namespace std;
int dp[105][1005];
int p[105], m[105];
int main() {int N, X;while (~scanf("%d %d", &N, &X)) {for (int i = 1; i <= N; i++) {cin >> p[i] >> m[i];}memset(dp, 0, sizeof(dp));for (int i = 1; i <= N; i++) {for (int j = 1; j <= X; j++) {if (p[i] > j)dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i]] + m[i]);}}cout << dp[N][X] << endl;}return 0;
}

代码二：(一维DP，C++)

#include<bits/stdtr1c++.h>
using namespace std;
int main() {int n, x;while (cin >> n >> x) {vector<int> p(105), m(105), dp(1005);for (int i = 1; i <= n; i++) cin >> p[i] >> m[i];for (int i = 1; i <= n; i++)for (int j = x; j >= 1; j--)dp[j] = (j < p[i] ? dp[j] : max(dp[j], dp[j - p[i]] + m[i]));cout << dp[x] << endl;}return 0;
}

代码三（一维DP，Python）

while True:try:n, x = map(int, input().split())p, m, dp = [0] * 105, [0] * 105, [0] * 1005for i in range(1, n + 1):p[i], m[i] = map(int, input().split())for i in range(1, n + 1):for j in range(x, 0, -1):if j < p[i]:dp[j] = dp[j]else:dp[j] = max(dp[j], dp[j - p[i]] + m[i])print(dp[x])except EOFError:break

2.最少硬币问题

题目描述：
设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。

输入格式：
输入数据第一行中只有1个整数给出n的值,第2行起每行2个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。

输出格式：
输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出-1。

样例
输入：

输出：

代码：

#include<bits/stdtr1c++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
struct node {int t, c;
} c[10];
int main() {int n, m, dp[20005];cin >> n;for (int i = 1; i <= n; i++) cin >> c[i].t >> c[i].c;cin >> m;for (int i = 1; i <= m; i++) dp[i] = inf;for (int i = 1; i <= n; i++)for (int j = 1; j <= c[i].c; j++)for (int k = m; k >= c[i].t; k--)dp[k] = min(dp[k], dp[k - c[i].t] + 1);cout << (dp[m] == inf ? -1 : dp[m]);return 0;
}

3.数字三角形问题

题目描述：
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

输入格式：
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。

输出格式：
输出数据只有一个整数，表示计算出的最大值。

样例
输入：

输出：

代码一（C++）：

#include<bits/stdtr1c++.h>
using namespace std;
int dp[105][105];
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 - 1; i >= 1; i--) {for (int j = 1; j <= i; j++) {dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);}}cout<<dp[1][1];return 0;
}

代码二（Python）

n, a = int(input()), []
for i in range(n):a.append(list(map(int, input().split())))
for i in range(n - 2, -1, -1):  # # 自下而上,也就是从倒数第2行到第0行for j in range(i + 1):  # 第i行有i+1个数字a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j]  # 每次转移从它的正下方或者右下方转移
print(a[0][0])

4.最长公共子序列问题

题目描述：
给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

输入格式：
输入数据有多组，每组有两行，每行为一个长度不超过500的字符串（输入全是大写英文字母（A,Z）），表示序列X和Y。

输出格式：
每组输出一行，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出0。

样例
输入：

ABCBDAB
BDCABA

输出：

代码一（C++）：

#include <bits/stdtr1c++.h>
using namespace std;
char s1[505], s2[505];
int dp[505][505];
int main() {while (~scanf("%s\n%s", s1 + 1, s2 + 1)) {memset(dp, 0, sizeof dp);int n = strlen(s1 + 1), m = strlen(s2 + 1);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}cout << dp[n][m] << endl;}return 0;
}

代码二（Python）

while True:try:s1 = input()s2 = input()n, m = len(s1), len(s2)dp = [[0] * (m + 1) for _ in range(n + 1)]  # 二维dp数组初始化for i in range(1, n + 1):for j in range(1, m + 1):if s1[i - 1] == s2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1 # s1与s2字符相同时,LCS长度+1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # s1与s2字符不同时 返回s1或s2向前减少一位之后的LCS中的较大者print(dp[n][m])except EOFError:break

5.石子合并问题

题目描述：
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
对于给定n堆石子,计算合并成一堆的最小得分和最大得分。

输入格式：
输入数据的第1行是正整数n，1≤n≤100，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。

输出格式：
输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。

样例
输入：

4
4 4 5 9

输出：

43
54

代码一（C++）：

#include<bits/stdtr1c++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int a[300], s[300];
int Min[300][300], Max[300][300];
int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];a[i + n] = a[i];}for (int i = 1; i < 2 * n; i++) {s[i] = s[i - 1] + a[i];}for (int i = 2 * n - 1; i >= 1; i--) {for (int j = i + 1; j < i + n; j++) {Min[i][j] = inf;for (int k = i; k < j; k++) {Min[i][j] = min(Min[i][j], Min[i][k] + Min[k + 1][j] + s[j] - s[i - 1]);Max[i][j] = max(Max[i][j], Max[i][k] + Max[k + 1][j] + s[j] - s[i - 1]);}}}int minv = inf, maxv = 0;for (int i = 1; i <= n; i++) {minv = min(minv, Min[i][i + n - 1]);maxv = max(maxv, Max[i][i + n - 1]);}cout << minv << endl << maxv;return 0;
}

代码二（Python）：

dp1 = [[1e9] * 180 for _ in range(180)]
dp2 = [[-1] * 180 for _ in range(180)]
st, Sum = [0] * 180, [0] * 180
n = int(input())
ls = list(map(int, input().split()))
for i in range(1, n + 1):st[i + n] = st[i] = ls[i - 1]dp1[i][i], dp2[i][i], dp1[i + n][i + n], dp2[i + n][i + n] = 0, 0, 0, 0
for i in range(1, 2 * n):Sum[i] = Sum[i - 1] + st[i]
for i in range(2, n + 1):for j in range(1, 2 * n - i + 1):e = j + i - 1for k in range(j, e):dp1[j][e] = min(dp1[j][e], dp1[j][k] + dp1[k + 1][e] + Sum[e] - Sum[j - 1])dp2[j][e] = max(dp2[j][e], dp2[j][k] + dp2[k + 1][e] + Sum[e] - Sum[j - 1])
Min, Max = 1e9, -1
for i in range(1, n + 1):Min = min(Min, dp1[i][i + n - 1])Max = max(Max, dp2[i][i + n - 1])
print("%d\n%d" % (Min, Max))