數字三角形（暴力備忘錄和動态規劃）

文章目錄

• 前言
• 一、#什麼是數字三角形及要解決的問題
• 二、數組存入
• 三、方法及代碼
• • 1.暴力（遞歸）
  • 2.備忘錄法
  • 3.動态規劃（填表法）
• 總結與進一步

前言

提示：這裡可以添加本文要記錄的大概内容：

例如：今天我們學習一下數字三角形的最優路徑，用到了暴力（遞歸），備忘錄法，和動态規劃。其實備忘錄法也是動态規劃的一種，又叫查表法。主要的差别看下文。

一、#什麼是數字三角形及要解決的問題

示例：

1. 數字三角形其實是一堆無序的數字組成一個三角形

2. 要解決的問題

   我們要解決的問題就是怎麼樣選擇一個最優路徑，（從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數加起來可以得到一個和，和最大的路徑稱為最佳路徑。編寫一個程式求出最佳路徑上的數字之和。）路徑上的每一步隻能從一個數走到下一層上和它最近的左邊的數或者右邊的數。

   上圖的最優路徑就是

   

   7+3+8+7+5=30，這條路徑是最大路徑。

二、數組存入

我們可以用二維數組存這些資料。

7

3 8

8 1 2

2 7 4 4

4 5 2 6 5

本來的左邊的數或者右邊的數就變成了直接下面和右下的資料

//n是該二維數組的層數
int a[][]=new int[n][n];

           

三、方法及代碼

1.暴力（遞歸）

暴力意味着窮舉，意思是将每一個路徑都找出來。但暴力也需要有技巧的暴力。在這裡我們就用到了遞歸。

我們先把這個數組劃分為一個個簡單的數組，如

根據規定，隻能走下一層最近的兩個數字，也就是說每個數字隻存在兩種情況，（7的選擇：3or8；3的選擇：8or1）

那我們可以用遞歸的方法來決定最優路徑（自頂向下分解問題，自底向上求解）窮舉路徑。

我們直接看最下面一行和倒數第二層資料。2的最優路徑是5，7的最優路徑是6，4的最優路徑是6，4的最優路徑是6。

我們直接看倒數第二層資料和倒數第三層資料。8的最優路徑是2+5，1的最優路徑是7+6，2的最優路徑是4+6。

其實，一個數的最優路徑就是這個本身的值再加上直接下面和右下資料的最優路徑（遞歸思想）

而遞歸的結束條件就是遞歸到了最上面一層。

代碼如下（示例）：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  while(in.hasNext()) {
  //資料層數
      int n=in.nextInt();
      int a[][]=new int[n][n];
      for(int i=0;i<n;i++){
       for(int j=0;j<=i;j++){
        a[i][j]=in.nextInt();
       }
      }
      //從第一層開始遞歸即a【0】【0】
        System.out.println(solve(n,a,0,0));
   }
 }
     private static int solve(int n,int[][] a，int i,int j) {
  // TODO Auto-generated method stub
  //超出a的範圍，結束遞歸
  if(i==n){return 0;}
  //選擇下一層直下面的路徑小還是右下的路徑小
  else{return b[i][j]=a[i][j]+Math.max(solve(n,a,b,i+1,j),solve(n,a,b,i+1,j+1));
  } }
 }  
           

2.備忘錄法

在遞歸的基礎上，備忘錄法很簡單（其實就是遞歸+判斷）。

我們在遞歸的時候會發現3=max(8的最短路徑,1的最短路徑)

8=max(1的最短路徑,2的最短路徑)

1的最短路徑,我們使用了兩次，而在上面的代碼中我們也計算了兩次1的最短路徑。這就拉長了時間。

意識到這個問題，我們可以不可以建立一個表，把已經計算過的資料寫入表中，下次再計算之前先查表，如有該資料我們就直接使用，沒有在計算。

代碼如下（示例）：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  while(in.hasNext()) {
      int n=in.nextInt();
      int a[][]=new int[n][n];
      //建立一個新的數組b，用作備忘錄表
      int b[][]=new int[n][n];
      for(int i=0;i<n;i++){
       for(int j=0;j<=i;j++){
        a[i][j]=in.nextInt();
       }
      }
       //将備忘錄中的值全定義為-1；
      for(int i=0;i<n;i++){
       for(int j=0;j<=i;j++){
        b[i][j]=-1;
       }
      }
      System.out.println(solve(n,a,b,0,0));
     // //驗證是否存入備忘錄
     //aa(b,n);
 }
 }
   //驗證是否存入備忘錄
 private static void aa(int[][] b,int n) {// TODO Auto-generated method stub
 for(int i=0;i<n;i++){
    for(int j=0;j<=i;j++){
         System.out.print (b[i][j]+" ");
          }
         System.out.println ( );
         }
         }
         private static int solve(int n,int[][] a,int[][] b,int i,int j) {
  // TODO Auto-generated method stub
  //超出a的範圍，結束遞歸
  if(i==n){return 0;}
  //如何備忘錄中該位置的值為-1，即還未計算，就計算,在存入備忘錄；若有值，說明之前計算過該值，直接用b[i][j];
  if(b[i][j]==-1){
   return b[i][j]=a[i][j]+Math.max(solve(n,a,b,i+1,j),solve(n,a,b,i+1,j+1));
  }else{
   return b[i][j];
   }
  }
 }  
           

3.動态規劃（填表法）

查表有點麻煩要先填表再查。若我們要改進，該怎麼辦呢？能不能直接填表呢。當然可以。

我們建立一個新的二維數組，将該位置數組的最短路徑直接填入，最後b[0][0]就是我們要求的最優路徑啦。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner in=new Scanner(System.in);
  while(in.hasNext()) {
      int n=in.nextInt();
      int a[][]=new int[n][n];
      //建立一個新的數組b，用作表
      int b[][]=new int[n][n];
      for(int i=0;i<n;i++){
       for(int j=0;j<=i;j++){
        a[i][j]=in.nextInt();
        }
        }
        //将a的最後一行直接寫入b；
      for(int j=0;j<n;j++){
    b[n-1][j]=a[n-1][j];
   }
   //
      for(int i=n-2;i>=0;i--){
       for(int j=0;j<=i;j++){
        //b[i][j]的值等于a[i][j]+此時（i,j)下面一行的正下方和右下方較大的值；
        b[i][j]=a[i][j]+Math.max(b[i+1][j],b[i+1][j+1]);
       }
      }
       System.out.println(b[0][0]);
 
 }
 }
}
           

總結與進一步

提示：動态規劃比備忘錄更簡潔就在于前者不需要查表。

上面的是自底向上求解（遞歸），那我們用動态規劃試試自頂向下求。

注意：該位置資料最佳路徑=max（左上角資料最優路徑，直接上層資料最優路徑）；

在計算最左側資料的時候沒有其左上角資料；是以我們在定義數組的時候要注意第一層資料7的位置應該是a[1][1。]其他沒有資料的位置填入0.