动态规划之三角形

动态规划问题：
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

说道递推是我新学到的，但在我们平常却经常用到，关于递推和递归就差一个字，他们的区别是：

    1，从程序上看，递归表现为自己调用自己，递推则没有这样的形式。

    2，递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题是逆向的。      递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。 

    3，递归中，问题的n要求是计算之前就知道的；      递推可以在计算中确定，不要求计算前就知道n。 

    4，一般来说，递推的效率高于递归（当然是递推可以计算的情况下） 

    5，在代码运行机制中，递归是先调用一直从从栈的头开始到末尾结束，但出栈顺序确实相反的，递推不同，他更符合人类逻辑，是正向往下进行，一直到结束。

其实递归和递推在动态规划中都可以使用，但是每当有分支出现时，总会出现重复的子问题重复计算，浪费时间哦！
斐波那契数列
1 1 2 3 5 8 13 21 33 54 …
动态规划之三角形

#include <iostream>    
#include <algorithm>   
using namespace std;   
  
#define MAX 101   
int D[MAX][MAX];     
int n;    
int maxSum[MAX][MAX];  
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
      
    int i,j;      
    cin >> n;      
    for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
		 	cout<<"D["<<i<<"]["<<j<<"]个：";        
        	cin >> D[i][j]; 
		}    
    for( int i = 1;i <= n; ++ i )
	{
		maxSum[n][i] = D[n][i]; 
	}       
            
    for( int i = n-1; i>= 1;  --i )
	{
		for( int j = 1; j <= i; ++j )           
            maxSum[i][j] = max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];
	}                 
    cout << maxSum[1][1] << endl;    
   
	}     
        
}//主方法结束

加油，自己的写的一些想法，刚开始写的时候总会觉得患得患失的。慢慢会好的。这是我学长给我讲的很好！
第一、定位

在成立博客之初，一定要有个明确定位。不要为了涵盖范围广而弄成一个所谓的“门户”网站。好的博客不在于信息量有多广，而是有多专。原因有二：首先、博客基本上是个人或者几个人运维，很难有精力做好一个门户网站；其次、如果你是用户，你会选择sina、网易还是你的“门户网站”？

第二、质量

当初我有个困恼，就是我是转载还是原创。转载，不容易收录。原创，自己的阅历有限，写不出好的文章。就目前来说，我认为文章的原创或是转载并不重要。其一，百度收录不仅仅看的是否是原创，转载也要看质量和定位，最好带上点睛的评语；其二、一定要注重文章可读性。如果一篇文章既没价值，也没有爱，谁会读下去呢？尽管是原创的文章。

第三、体验

在做好了上面两方面，再考虑体验的问题也不迟。用户体验会给用户带来阅读时的高舒服度。

动态规划之三角形

相关推荐