首页 > 代码库 > 【动态规划初级】动态规划入门 poj1163 The Triangle

【动态规划初级】动态规划入门 poj1163 The Triangle

2024-07-05 07:26:40   230人阅读

动态规划

我在学习算法的时候，就被动态规划搞得是一头雾水，这几日终于是弄明白是怎么回来。

明白之后我才发觉我以前就碰到过一道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，它并不依赖于上一步的决策，

而动态规划则是不同的，它的每一步进行决策时是依赖于上一步的决策的。每一步的决策的相关的，是可回遡的。

比如在找第一行7的下一个节点，它能有两个种决策，一个是第二行的3，一个是第二行的8。由于有这两种可能性，所以在进行，第二行至第三行的决策的时候，是依赖于上一步决策的。而且由于每一次决策所以产生的可能的状态，都被保荐着，所以当所以找的决策不是最优决策时，可以回遡。

越说越麻烦了，一句话，就是动态规划其实是以牺牲空间来换取决策的正确性.


来源： <http://6460646.blog.163.com/blog/static/27779875200732894639165/>


The Triangle
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 36089 Accepted: 21581

Description

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5

(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right. 

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. Characterize the structure of an optimal solution.  有公共的子问题
2. Recursively define the value of an optimal solution.  能递归的定义子问题的最优解
3. Compute the value of an optimal solution in a bottom-up fashion. 能自底向上的求解
4. Construct an optimal solution from computed information.   能通过计算信息构造出最优解

来源： <http://sun.solrex.org/?p=166>
 
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]);
    }
    
}

 

来自为知笔记(Wiz)


联系
我们