个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
24
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++数字三角形问题与dp算法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
题目：数字三角形 。
题目介绍：如图所示的数字三角形，要求从最上方顶点开始一步一步下到最底层，每一步必须下一层，求出所经过的数字的最大和.
输入：第一行值n，代表n行数值；后面的n行数据代表每一行的数字.
输出：经过数字的最大和.
例:
输入:
4 。
1 。
3 2 。
4 10 1 。
4 3 2 20 。
输出:
24 。
分析：这也是一个典型的贪心算法无法解决的问题，同样可以用动态规划（dp算法）来解决。把边界数字首先初始化到结果矩阵中，再根据状态方程完成结果矩阵的遍历。需要注意的就是数组不是矩形而是三角形，与传统的状态方程相比需要做点改进.
数组编号:
状态方程：p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]} 。
代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include <iostream>
using
namespace
std;
int
main()
{
int
i;
int
n;
cin >> n;
int
**p =
new
int
*[n];
for
(i = 0; i < n; i++)
{
p[i] =
new
int
[n];
}
for
(i = 0; i < n; i++)
{
for
(
int
j = 0; j <= i; j++)
{
cin >> p[i][j];
}
}
for
(i = 1; i < n; i++)
{
p[i][0] += p[i - 1][0];
}
for
(i = 1; i < n; i++)
{
p[i][i] += p[i - 1][i - 1];
}
for
(i = 2; i < n; i++)
{
for
(
int
j = 1; j < i; j++)
{
p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
}
}
for
(i = 0; i < n; i++)
{
for
(
int
j = 0; j <= i; j++)
{
cout << p[i][j] <<
" "
;
}
cout << endl;
}
}
|
结果如下图:
。
所以最下层的数字和最大值是24. 。
总结 。
以上所述是小编给大家介绍的C++数字三角形问题与dp算法，希望对大家有所帮助，如果大家有任何疑问欢迎给我留言，小编会及时回复大家的！ 。
原文链接：https://www.cnblogs.com/ljy1227476113/archive/2018/09/02/9572328.html 。
最后此篇关于C++数字三角形问题与dp算法的文章就讲到这里了,如果你想了解更多关于C++数字三角形问题与dp算法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
24
4
0
我学过这两种DP方式，现在很迷茫。不同情况下我们如何选择？而且我发现在大多数情况下，自上而下对我来说更自然。谁能告诉我如何做出选择。 PS:这篇文章我看过older post但仍然感到困惑。需要帮忙。
我在想是否有某种通用的方法可以将自上而下的动态编程转换为自下而上的编程。 我们能否想出某种机制来提供正式的方式，通过这种方式我们可以将自上而下的 DP 转换为自下而上的 DP。 注意:我是动态规划的初
在我的 xml 中，我在 TextView 上有这个: android:textSize="18dp"(是的，我知道 dp 不适合文本，但这不是重点) 我还有其他一些以编程方式创建的 TextView
假设我正在为屏幕尺寸等于或大于 600dp 的设备开发不同的布局。我想使用 post android 3.2 资源限定符。我创建了一个名为 layout-sw600dp 的文件夹并将我的布局放在那里，
最近我在 https://leetcode.com/problems/palindrome-partitioning-ii/ 上遇到了这个问题: 给定一个字符串s，划分s使得划分的每个子串都是回文。
我已经尝试使用 admob 大约 4 个小时了，现在真的卡住了。我得到: Not enough space to show ad. Needs 320x50 dp, but only has 288
我正在尝试将可变数量的像素计算为与密度无关的像素，反之亦然。 这个公式 (px to dp): dp = (int)(px/(displayMetrics.densityDpi/160)); 不适用于
我正在从头开始创建一个 HTML 页面，并在其中动态放置值，然后将其显示在 WebView 中。 我正在尝试在 WebView(作为 HTML)中复制 ActionBar(出现在应用程序的其他 Act
我正在使用 the 4.17.37 of Bootstrap 3 Datepicker - eonasdan datepicker 我有一个正确显示的内联日期选择器，我只会使用天模式，所以我使用以下代
我正在尝试将智能横幅广告添加到我的 fragment 布局中，但我不断得到的是“没有足够的空间来展示广告。需要 320x50 dp，但只有 309x0 dp”。 这是我的 fragment 布局。
我在关于 http://developer.android.com/guide/practices/screens_support.html 的一些不幸的歧义中迷失了方向，而且我找不到澄清问题的 st
写在前面 $ DP $，是每个信息学竞赛选手所必会的算法，而 $ DP $ 中状态的转移又显得尤为关键。本文主要从状态的设计和转移入手，利用各种方法对朴素 $ DP $ 的时间复杂度和空间复杂度进行
我试图理解一种著名的正则表达式匹配 DP 算法。以防万一，人们不知道这是描述和算法。 '.' Matches any single character. '*' Matches zero or mor
注意：是的，我知道Android中还有其他处理按钮的方法，但这只是一个示例来说明我的问题（实际的按钮要复杂得多）。因此，请不要在为Android中的按钮提供其他解决方案时回信，我正在寻找PaintCo
Closed. This question needs to be more focused。它当前不接受答案。 想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。
我正在测试 Samsung Galaxy Note 3根据文档，它是 1080 x 1920 像素(~386 ppi 像素密度)。我想弄清楚 dp 中的屏幕宽度 是多少，以便我可以正确应用并检查 ne
所以我现在完全迷路了，当用户通过Accessibility -> Font size 将字体大小时设置为Huge 时，文本大小会破坏我的 UI，所以为了快速修复 我决定将所有文本大小更改为 dp 而不
更新:我发现了我的问题。我已经为不同的分辨率定义了单独的可绘制资源，但我不知道我必须为不同的屏幕尺寸创建不同的布局。我想我应该更全面地阅读“支持多屏幕”页面。遇到此问题的任何其他人，请阅读整个页面:
阅读这篇文章(http://developer.android.com/guide/practices/screens_support.html)后，我在 xml 文件中使用 dp 单元开发了一个完整
该问题需要计算特定成本的硬币变化次数。 例如，如果我有 50, 20, 10, 5, 1 的硬币值(value)，我可以形成以下成本: 5 => (5), (11111), 这是2种方式。 10 =>
我是一名优秀的程序员,十分优秀！