A - Frog 1（线性dp）

题目 题意：有一排高等不一的柱子，一个青蛙从一头跳到另一头，一次最多跳一次或两个柱子，记录高度变化的最小总和；

简单的线性DP： 状态转移方程：dp[i]=Math.min(dp[i-2]+Math.abs(a[i]-a[i-2]),dp[i-1]+Math.abs(a[i]-a[i-1])); 初始化：dp[1]=0；dp[2]=Math.abs(a[2]-a[1]);

AC代码：

import java.util.*; public class Main { static Scanner sc=new Scanner(System.in); public static void main(String[] args) { int n=1; for(int i=0;i<n;i++) { show(); } } private static void show() { int n=sc.nextInt(); int dp[]=new int [n+1]; int a[]=new int [n+1]; for(int i=1;i<=n;i++) { a[i]=sc.nextInt(); } dp[1]=0; dp[2]=Math.abs(a[2]-a[1]); for(int i=3;i<=n;i++) { dp[i]=Math.min(dp[i-2]+Math.abs(a[i]-a[i-2]),dp[i-1]+Math.abs(a[i]-a[i-1])); } System.out.println(dp[n]); } }

感觉DP要多堆题