小编给大家分享一下c#如何实现数字三角形,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
公司主营业务:网站建设、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出晋江免费做网站回馈大家。数字三角形问题。有一个由非负数组成的三角形,如图所示。
从第一行开始,每次可以往左下或者右下走一格,直到走到最下行,把沿途经过的数全部加起来,如何走才能使得这个和大?
我们最常规的想法:就是利用回溯发,将每一条路径都遍历一遍,然后选出最长的路径。
此题更高效的算法是动态规划。把当前位置(i,j)看成一个状态,然后定义指标函数d(i,j)为从格子(i,j)出发的能得到的大的和(包括次格子本身),那么本题就转化成了求d(1,1)。
在动态规划的题目里,状态转移方程无疑是非常重要的,下面我们来看看状态转移方程d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)}其中a(i,j)表示每个圆形的数字
下面给出代码
#include#include using namespace std; int value[4][4]; int dp[4][4]; int main() { for(int i=0;i<4;i++) { for(int j=0;j<=i;j++) cin>>value[i][j]; } for(int i=0;i<4;i++) dp[3][i]=value[3][i]; for(int i=2;i>=0;i--) for(int j=0;j<=i;j++) dp[i][j]=value[i][j]+max(dp[i+1][j],dp[i+1][j+1]); cout< 以上是“c#如何实现数字三角形”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注创新互联行业资讯频道!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:c#如何实现数字三角形-创新互联
文章位置:http://njwzjz.com/article/diipde.html