跑步最高分算法（动态规划）-“奋斗杯”编程大赛题目
- 0、题目
- 1、思考
-
- 1.1 数组定义
- 1.2 初始化
- 1.3 状态转移
- 1.4 空间复杂度优化
- 2 代码实现
-
- 2.1 go语言实现
- 2.2 go语言空间复杂度优化实现
- 2.3 java实现
- 2.4 java空间复杂度优化实现
周末去参加了个“奋斗杯”上海市青年计算机程序设计大赛，水了个二等奖。这是其中一道题，因为时间不够没做出来，思路都对，差了一点就完成了。动态规划一直是我的弱项，趁此机会，把它记录下来。
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);
}
