目錄

1129遊園禮物動态規劃題解

by 2020郭駿羽

1.算法選擇

2-1 思路——順推法

2-1.思路——順推法 

2-1.思路——順推法

2-1.核心代碼——順推法

2-2 思路——逆推法

2-2 逆推法：思路

2-2 逆推法：核心代碼

1129遊園禮物動态規劃題解

by 2020郭駿羽

1.算法選擇

• 不能用貪心。貪心的缺點：目光短淺。
• DP題目，先做了1172和1124再說。
• 但是你若是用記搜也不攔你。
• 以下提供順推法和逆推法。

2-1 思路——順推法

2-1.思路——順推法 

√ 1.定義數組f[i][j][2]

√ 2. f[i][j][0]代表從上往下到達i行j列這個點所能達到的和的最大值,其中0表示在f[i][j]這狀态這之前尚未使用雙倍福利。

√ 3.同理，f[i][j][1]表示在這之前（包括目前 狀态）使用過了雙倍福利。

√ 4.初始化為f[i][j][0]=a[i][j],f[i][j][1]=a[i][j]*2;

√ 5.從上往下到達（i，j）這個點所能達到的和的最大值，即為其上方和左上方兩個數中大的那個加上它本身的值。

2-1.思路——順推法

• 6.在每次循環執行時，都要計算f[i][j][0]與f[i][j][1]的狀态。
• 7.計算f[i][j][0]并不難，f[i][j][0]=max(f[i-1][j][0],f[i-1][j-1][0])+a[i][j];
• 8.計算f[i][j][1]的時候，有兩個情況： （1）在這之前并沒有使用雙倍福利，則本次使用了。 （2）在這之前已經使用了雙倍福利。
• 9.最後輸出最下一層的最大值。

2-1.核心代碼——順推法

• 1.計算f[i][j][0]:
•         F[i][j][0]=max(f[i-1][j-1][0],f[i-1][j][0])+a[i][j];
• 2.計算f[i][j][1]（兩種情況中取優解）:
•         F[i][j][1]=max(max(max(f[i-1][j][0],f[i-1][j-1][0])+a[i][j]*2,max(f[i-1][j][1],f[i-1][j-1][1])+a[i][j]))；

2-2 思路——逆推法

• 我用的逆推法，其實等同于順推。
• 不多說什麼，手動給大家模拟普通數字金字塔。

      1

    6  9

  8  4  7 ☚從這一層開始

6  3  8  2

      ↓

      1

    6  9

14  4  7

6  3  8  2

• 8可以走到6或3，将8增加max(6,3)。
• 由此可推DP式：f[i][j]=max(f[i+1][j],f[i+1][j+1])

      1

    6  9

14 12 15

6  3  8  2

推出第三行的狀态。

      1

   22 24

14 12 15

6  3  8  2

逐漸往上推

     25 ←最後輸出頂部

   22 24

14 12 15

6  3  8  2

2-2 逆推法：思路

與順推法基本相同。

2-2 逆推法：核心代碼

• f[i][j][0]=max(f[i+1][j][0],f[i+1][j+1][0])+a[i][j];
• f[i][j][1]=max(max(f[i+1][j][0],f[i+1][j+1][0])+a[i][j]*2,max(f[i+1][j][1],f[i+1][j+1][1])+a[i][j]);
• 本部分詳解請見順推法的核心代碼。

沒啦，還看？

既然都到這兒了，看看我的部落格吧。