本文主要是介绍poj1163 The Triangle--动态规划入门（动态规划和贪心的去区别），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;int D[101][101];
int n;
int maxSum[101][101];
int main(){int i,j;cin >> n;for(i=0;i<n;i++)for(j=0;j<=i;j++){cin >> D[i][j];}for( int i = 0;i < n; ++ i ){maxSum[n-1][i] = D[n-1][i];}for( int i = n-1; i>=0; --i )for( int j = 0; j < i; ++j )maxSum[i-1][j] = max(maxSum[i][j],maxSum[i][j+1]) + D[i-1][j];cout << maxSum[0][0] << endl;
}
分析：
我在学习算法的时候，就被动态规划搞得是一头雾水，这几日终于是弄明白是怎么回来。
明白之后我才发觉我以前就碰到过一道ACM题,大意是这样的:
有这样形式的一种排列:
例如:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从顶至下找一条路径，使得这条路径上的数字之和最大,而且每一步只能向左下或右下找，直到到最后一行。
比如：第二行的3只能找第三行8或者1。
上面例子的最大一条路径是:7-3-8-7-5;总和30（原题：http://acm.fzu.edu.cn/problem.php?pid=1004)
如果按照贪婪算法，从上往下找，则最佳路径应该是7-8-1-7-5;总和28
可见贪婪算法在此是行不通的。我们可以试着从下往上找，倒数两行:
2 7 4 4
4 5 2 6 5
我们先对最后一行相邻的两个数字进行比较，大的加到上一行的数字上。则4-5比较，5较大，则倒数第二行2+5;
5-2比较，5较大，则倒数第二行7+5,如此类推：则倒数第二行就是：
7 12 10 10;
然后依此类推：直到第一行，就得到了最大的和，当然原题没有要求我们找路径，所以不用记录路径.
其实这就是一种动态规划的应用。
它与贪婪法的区别,在此也能明显地看出:
1、 贪婪法，采取的是自顶向下，逐步找局部最优，从而来达到，整体最优。而动态规划则是从下往上倒推。
2、贪婪法，在进行决策时并不依赖于上一步的决策。每一步的决策都是单独的，确定的，不可回遡的。
比如在找第一行7的下一个节点，那肯定是第二行的8，它是确定的，不可回遡的。而第二行的8的下一个结点肯定是1，它并不依赖于上一步的决策，
3、而动态规划则是不同的，它的每一步进行决策时是依赖于上一步的决策的。每一步的决策的相关的，是可回遡的。
比如在找第一行7的下一个节点，它能有两个种决策，一个是第二行的3，一个是第二行的8。由于有这两种可能性，所以在进行，第二行至第三行的决策的时候，是依赖于上一步决策的。而且由于每一次决策所以产生的可能的状态，都被保荐着，所以当所以找的决策不是最优决策时，可以回遡。
越说越麻烦了，一句话，就是动态规划其实是以牺牲空间来换取决策的正确性。
| The Triangle
Description 7 Input Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99. Output Your program is to write to standard output. The highest sum is written as an integer. Sample Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30 Source IOI 1994 来源： <http://poj.org/problem?id=1163> |
这个最简单的动态规划题目满足了动态规划的四个条件：
1. 有公共的子问题
2. 能递归的定义子问题的最优解
3. 能自底向上的求解
4. 能通过计算信息构造出最优解
Java语言实现：
import java.util.Scanner;
public class Main{
public static void main(String []args){
Scanner scanner=new Scanner(System.in);
int n;
n=scanner.nextInt();
int mar[][]=new int[n+1][n+1];
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
mar[i][j]=scanner.nextInt();
}
}
int max=0;
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
max=mar[i+1][j]>mar[i+1][j+1]?mar[i+1][j]:mar[i+1][j+1];
mar[i][j]+=max;
}
}
System.out.println(mar[0][0]);
}
}
这篇关于poj1163 The Triangle--动态规划入门（动态规划和贪心的去区别）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
