周末去參加了個“奮斗杯”上海市青年計算機程式設計大賽，水了個二等獎，這是其中一道題，因為時間不夠沒做出來，思路都對，差了一點就完成了，動態規劃一直是我的弱項，趁此機會，把它記錄下來，

0、題目

A同學參加一個跑步比賽，路徑分為n段，每段有不同的分值，如果該段走路不得分；該段慢跑則得相應的分數；該段快跑則得對應分數的兩倍，但下一段必須走路，求A同學跑完全程可以獲得的最高分，

如總共有4段路， 對應的分值為 [1, 2, 3, 4] ，則最高分的跑法是，前三段慢跑，最后一段快跑，即 1+2+3+4*2 = 14 ，

輸入對應路段分值的陣列，輸出獲得的最高分，

• Golang
• Java

1、思考

狀態轉移，經典的動態規劃演算法，

1.1 陣列定義

定義二維陣列 dp[i][j] ,

• 值為當前狀態下可以獲得的最高分；
• i 為路段的索引；
• j 為本段跑步狀態，當 j=0 為走路，j=1 為慢跑，j=2 為快跑，

1.2 初始化

dp[0][0] = 0
dp[0][1] = points[0]
dp[0][2] = points[0] * 2

1.3 狀態轉移

• 本段選擇走路，則上一段可以是走路、慢跑、快跑，所以可得 dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
• 本段選擇慢跑，則上一段可以是走路、慢跑，所以 dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + 當前段得分
• 本段選擇快跑，則上一段可以是走路、慢跑，所以 dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 當前段得分的兩倍

最終只需要找出dp[n-1]里最大的值就行，

1.4 空間復雜度優化

dp寫完發現，最終結果只和上一次的結果有關，之前計算出的值就沒必要儲存了，基于此，只需要定義3個變數記錄前一段三種狀態所能獲得的最高分即可，空間復雜度可以從O(n)優化到O(1)，

定義prevWalk, prevSlowRun, prevFastRun分別為上一段走路、慢跑、快跑獲得的總共最高分，
接下來就和上面一樣狀態轉移就行

2 代碼實作

2.1 go語言實作

//go語言實作
func run(points []int) int {
	length := len(points)
	if length == 0 {
		return 0
	}

	//dp[i][j]值為當前路段當前狀態獲得的最大總分數，i為路段的索引，j為本段狀態，其中0為本段走路，1為本段慢跑，2為本段快跑
	dp := make([][3]int, length)
	dp[0][0] = 0
	dp[0][1] = points[0]
	dp[0][2] = points[0] * 2
	for i := 1; i < length; i++ {
		dp[i][0] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]) //本段走路，上段可以是任何狀態
		dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + points[i]      //本段慢跑，上段只能是走路或者慢跑
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + points[i]*2    //本段快跑，上段只能是走路或者慢跑
	}
	return max(max(dp[length-1][0], dp[length-1][1]), dp[length-1][2])
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

2.2 go語言空間復雜度優化實作

func runBetter(points []int) int {
	length := len(points)
	if length == 0 {
		return 0
	}

	var prevWalk, prevSlowRun, prevFastRun = 0, points[0], points[0] * 2
	for i := 1; i < length; i++ {
		var walk, slowRun, fastRun int
		walk = max(max(prevWalk, prevSlowRun), prevFastRun) //本段走路，上段可以是任何狀態
		slowRun = max(prevWalk, prevSlowRun) + points[i]    //本段慢跑，上段只能是走路或者慢跑
		fastRun = max(prevWalk, prevSlowRun) + points[i]*2  //本段快跑，上段只能是走路或者慢跑
		prevWalk = walk
		prevSlowRun = slowRun
		prevFastRun = fastRun
	}
	return max(max(prevWalk, prevSlowRun), prevFastRun)
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

2.3 java實作

public static int run(int[] points){
    int n = points.length;
    if (n == 0){
        return 0;
    }
    //dp[i][j]值為當前路段當前狀態獲得的最大總分數，i為路段的索引，j為本段狀態，其中0為本段走路，1為本段慢跑，2為本段快跑
    int[][] dp = new int[n][3];
    //初始化
    dp[0][0] = 0;
    dp[0][1] = points[0];
    dp[0][2] = points[0]*2;
    for (int i = 1; i < n; i++) {
        dp[i][0] = Math.max(Math.max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);//本段走路，上段可以是任何狀態
        dp[i][1] = Math.max(dp[i-1][0],dp[i-1][1]) + points[i];     //本段慢跑，上段只能是走路或者慢跑
        dp[i][2] = Math.max(dp[i-1][0],dp[i-1][1]) + points[i] * 2; //本段快跑，上段只能是走路或者慢跑
    }
    return Math.max(Math.max(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
}

2.4 java空間復雜度優化實作

public static int run(int[] points){
    int n = points.length;
    if (n == 0){
        return 0;
    }
    //初始化
    int prevWalk = 0, prevSlowRun = points[0], prevFastRun = points[0] * 2;
    for (int i = 1; i < n; i++) {
        int walk = Math.max(Math.max(prevWalk, prevSlowRun), prevFastRun);//本段走路，上段可以是任何狀態
        int slowRun = Math.max(prevWalk, prevSlowRun) + points[i];     //本段慢跑，上段只能是走路或者慢跑
        int fastRun = Math.max(prevWalk, prevSlowRun) + points[i] * 2; //本段快跑，上段只能是走路或者慢跑
        prevWalk = walk;
        prevSlowRun = slowRun;
        prevFastRun = fastRun;
    }
    return Math.max(Math.max(prevWalk, prevSlowRun), prevFastRun);
}