數(shù)字三角形

鏈接：[USACO1.5] [IOI1994]數(shù)字三角形 Number Triangles

題目描述

觀察下面的數(shù)字金字塔。

寫一個程序來查找從最高點到底部任意處結(jié)束的路徑，使路徑經(jīng)過數(shù)字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

在上面的樣例中，從 $7\to 3\to 8\to 7\to 5$ 的路徑產(chǎn)生了最大權(quán)值。

輸入格式

第一個行一個正整數(shù) $r$ ,表示行的數(shù)目。

后面每行為這個數(shù)字金字塔特定行包含的整數(shù)。

輸出格式

單獨的一行,包含那個可能得到的最大的和。

樣例 #1

樣例輸入 #1

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

樣例輸出 #1

30

提示

【數(shù)據(jù)范圍】
對于 $100\%$ 的數(shù)據(jù)，$1\le r\le 1000$，所有輸入在 $[0,100]$ 范圍內(nèi)。

題目翻譯來自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

參考代碼

這道題就是很裸的DP，也是很經(jīng)典的入門題。我們先用記憶化搜索寫一遍，再來寫DP。

（1）記憶化搜索

我們首先讀取金字塔的行數(shù) r 和每行的數(shù)字，并存儲在二維數(shù)組 triangle 中。然后，我們使用記憶化搜索的深度優(yōu)先搜索函數(shù) dfs 來計算從金字塔頂部到底部的最大路徑和。

在 dfs 函數(shù)中，如果已經(jīng)計算過當(dāng)前位置到底部的最大路徑和，我們直接返回結(jié)果；如果已經(jīng)到達最后一行，我們返回當(dāng)前值；否則，我們返回從當(dāng)前位置到底部的最大路徑和，并將結(jié)果存儲在記憶化搜索數(shù)組 memo 中，以便后續(xù)使用。

最后，我們輸出最大路徑和。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
    // 快讀快寫
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StreamTokenizer in = new StreamTokenizer(br);
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    
    public static int[][] triangle;
    public static Integer[][] memo;  // 用于記憶化搜索的數(shù)組

    public static void main(String[] args) throws IOException {
        // 讀數(shù)據(jù)
        in.nextToken();
        int r = (int) in.nval;
        triangle = new int[r][];
        memo = new Integer[r][r];  // 初始化備忘錄
        for (int i = 0; i < r; i++) {
            triangle[i] = new int[i+1];
            for (int j = 0; j <= i; j++) {
                in.nextToken();
                triangle[i][j] = (int) in.nval;
            }
        }

        // 記憶化搜索
        int maxSum = dfs(0, 0, r);

        out.println(maxSum);
        out.flush();
        br.close();
        out.close();
    }

    public static int dfs(int i, int j, int r) {
        // 如果已經(jīng)計算過，直接返回結(jié)果
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        // 如果已經(jīng)到達最后一行，返回當(dāng)前值
        if (i == r - 1) {
            return memo[i][j] = triangle[i][j];
        }
        // 否則，返回從當(dāng)前位置到底部的最大路徑和
        return memo[i][j] = triangle[i][j] + Math.max(dfs(i + 1, j, r), dfs(i + 1, j + 1, r));
    }
}

記憶化搜索是一種優(yōu)化技術(shù)，主要用于優(yōu)化遞歸算法，避免重復(fù)計算相同的子問題。它的主要思路是將已經(jīng)計算過的子問題的結(jié)果存儲起來，當(dāng)再次遇到相同的子問題時，直接從存儲的結(jié)果中獲取，而不是重新計算。

（2）動態(tài)規(guī)劃

下面我們來看DP的解法：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer in = new StreamTokenizer(br);
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
    	// 讀數(shù)據(jù)
        in.nextToken();
        int r = (int) in.nval;
        int[][] triangle = new int[r][];
        for (int i = 0; i < r; i++) {
            triangle[i] = new int[i+1];
            for (int j = 0; j <= i; j++) {
                in.nextToken();
                triangle[i][j] = (int) in.nval;
            }
        }

        // 動態(tài)規(guī)劃
        int[][] dp = new int[r][r];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < r; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                } else if (j == i) {
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                }
            }
        }

		// 篩選答案（找到最后一行每個位置的路徑和最大值）
        int maxSum = dp[r-1][0];
        for (int i = 1; i < r; i++) {
            maxSum = Math.max(maxSum, dp[r-1][i]);
        }

        out.println(maxSum);
        out.flush();
        br.close();
        out.close();
    }
}

首先，我們定義狀態(tài) dp[i][j]，表示從金字塔頂部到第 i 行第 j 列的最大路徑和。

這里，i 和 j 的范圍都是從 0 開始的。

然后，我們需要找出狀態(tài)轉(zhuǎn)移方程（其實就是分析有多少種可能性）。

對于每一個位置 (i, j)，我們可以從其上方 (i-1, j) 或者左上方 (i-1, j-1) 移動過來。

因此，到達當(dāng)前位置的路徑和就是上方或者左上方的路徑和加上當(dāng)前位置的值，我們選擇其中的最大值作為當(dāng)前位置的路徑和。

具體來說，狀態(tài)轉(zhuǎn)移方程可以寫成如下形式：

• 當(dāng) j == 0（即在每一行的最左邊）時，只能從上方移動過來，所以 dp[i][j] = dp[i-1][j] + triangle[i][j]。
• 當(dāng) j == i（即在每一行的最右邊）時，只能從左上方移動過來，所以 dp[i][j] = dp[i-1][j-1] + triangle[i][j]。
• 當(dāng) 0 < j < i 時，可以從上方或者左上方移動過來，所以 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。

最后，我們返回最后一行中的最大值，即為可能得到的最大的和。

小結(jié)

動態(tài)規(guī)劃（DP）的本質(zhì)是對問題狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程的定義。動態(tài)規(guī)劃往往可以用來優(yōu)化具有重疊子問題的遞歸算法（跟記憶化搜索相似）。

遞歸算法的特點是自頂向下，從一個問題開始，分解為多個子問題來求解。而動態(tài)規(guī)劃則是自底向上，從最簡單的子問題開始，逐步解決更復(fù)雜的子問題，直到得到原問題的解。

因此，對于一個可以用動態(tài)規(guī)劃解決的問題，我們通常可以先嘗試用遞歸的方法解決，然后找出遞歸中的重疊子問題，再使用動態(tài)規(guī)劃的方法進行優(yōu)化，避免重復(fù)計算。

但是需要注意的是，雖然所有的動態(tài)規(guī)劃問題都可以從遞歸的角度來理解，但并不是所有的遞歸問題都可以用動態(tài)規(guī)劃來優(yōu)化。只有當(dāng)遞歸問題具有“重疊子問題”和“最優(yōu)子結(jié)構(gòu)”時，才能使用動態(tài)規(guī)劃進行優(yōu)化。文章來源地址http://www.zghlxwxcb.cn/news/detail-850549.html

到了這里，關(guān)于【題解 | 基礎(chǔ)動態(tài)規(guī)劃】：數(shù)字三角形的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！