旅游网站建设网站推广,电子商务网站建设与管理设计报告,临海市城乡建设规划局网站,wordpress wp loginpro引入 支付问题 假设有无限多的硬币#xff0c;硬币面值为1,5,11。现在需要支付15元#xff0c;问最少使用的硬币数#xff1f; 贪心策略#xff1a;1511*11*4#xff0c;145 真正的答案153*5 3 dp的两个性质 最优子结构无后效性 dp的两大要素 1.状态2.状态转移方程 思路…引入 支付问题 假设有无限多的硬币硬币面值为1,5,11。现在需要支付15元问最少使用的硬币数 贪心策略1511*11*4145 真正的答案153*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)15
2.先选5元的f(10)13
3.先选1元的f(14)15
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
*/
#includeiostream
using namespace std;
const int N1e410;
int dp[N];
int main()
{int w; cin w;//支付金额int mi 0x3f3f3f3f;//最小方案数字//时间复杂度Onfor (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到ij点最小体力花费2.状态转移方程 dp[i][j]min{dp[i-1][j],dp[i][j-1]}a[i][j] #includeiostream
using namespace std;
const int N1e310;
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 #includeiostream
using namespace std;
const int N1e210;
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;
}
