备战蓝桥杯 Day6(学习动态规划)

引入

支付问题

假设有无限多的硬币，硬币面值为1,5,11。现在需要支付15元，问最少使用的硬币数？
贪心策略：15=11*1+1*4，1+4=5
真正的答案15=3*5   3

dp的两个性质

• 最优子结构
• 无后效性

dp的两大要素

• 1.状态
• 2.状态转移方程

思路
1.状态 dp[i]--支付i元所用的最小方案数
2.状态转移方程 dp[i]=min{dp[i-11],dp[i-5],dp[i-1]}+1

代码实现

/*
状态f(w)支付w元所用的最少的硬币的数量
求f(15)
1.先选11元的：f(4)+1=5
2.先选5元的：f(10)+1=3
3.先选1元的：f(14)+1=5
f(15)=min{f(4)+1,f(10)+1,f(14)+1}求f(15)=min{f(4)+1,f(10)+1,f(14)+1}
求f(14)=min{f(3)+1,f(9)+1,f(13)+1}
求f(11)=min{f(0)+1,f(6)+1,f(10)+1}f(i)=min{f(i-11),f(i-5),f(i-1)}+1
*/
#include<iostream>
using namespace std;
const int N=1e4+10;
int dp[N];
int main()
{int w; cin >> w;//支付金额int mi = 0x3f3f3f3f;//最小方案数字//时间复杂度O（n）for (int i = 1; i <= w; i++)//注意下标{if (i >= 1) mi= min(mi,dp[i - 1])+1;if (i >= 5) mi= min(mi,dp[i - 5])+1;if (i >= 111) mi= min(mi,dp[i - 11])+1;dp[i] = mi;//打印dp表cout << "dp[" << i << "]=" << dp[i] << endl;}cout << dp[w] << endl;return 0;
}

二维格子问题

小明要回家，必须从左上角出发，回到右下角的家，每次向右或者向下走，每个点的值都代表体力消耗，从起点到家，最少体力开销

1 2 5

8 3 9

7 4 6

dp

• 1.状态 dp[i][j] 从起点（1,1）到（i，j）点最小体力花费
• 2.状态转移方程 dp[i][j]=min{dp[i-1][j],dp[i][j-1]}+a[i][j]

#include<iostream>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int a[N][N];//存体力
int main()
{int n; cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];//边界单独处理//行for (int j = 1; j <= n; j++)dp[1][j] = dp[1][j - 1] + a[1][j];//列for (int i = 1; i <= n; i++)dp[i][1] = dp[i-1][1] + a[i][1];for (int i = 2; i <= n; i++)for (int j = 2; j <= n; j++)dp[i][j] = min(dp[i - 1][j], dp[i][j-1]) + a[i][j];//dp表for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cout << dp[i][j] << "\t";}cout << endl;}cout << dp[n][n] << endl;return 0;
}

1288：三角形最佳路径问题

【题目描述】

如下所示的由正整数数字构成的三角形:

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边（右下方）的数。

【输入】

第一行为三角形高度100≥h≥1，同时也是最底层边的数字的数目。

从第二行开始，每行为三角形相应行的数字，中间用空格分隔。

【输出】

最佳路径的长度数值。

【输入样例】

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

【输出样例】

30

#include<iostream>
using namespace std;
const int N=1e2+10;
int dp[N][N], a[N][N], h, mx;//dp[i][j]:从(1,1)到(i,j)的所有路径中，数字加和最大的路径的数字加和。
int main()
{cin >> h;for (int i = 1; i <= h; ++i)for (int j = 1; j <= i; ++j)cin >> a[i][j];for (int i = 1; i <= h; ++i)for (int j = 1; j <= i; ++j)dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];for (int j = 1; j <= h; ++j)//求从(1,1)到第h行某位置路径上数字加和的最大值mx = max(mx, dp[h][j]);for (int i = 1; i <= h; ++i){for (int j = 1; j <= i; ++j){cout << dp[i][j] << " ";}cout << endl;}cout << mx;return 0;
}