线性动态规划模板

难度不大，线性动态规划的模板。题目就是指从一个地方走至多k步走到另一个地方所花费的代价，只需跟着题目走就可以推出状态转移方程dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
注意的是初学dp不要忘了把dp[1]定义为0
此外因为求最小值，所以用memset(dp, 0x3f3f3f3f, sizeof(dp));把dp全定义成最大值，我觉得memset很好用
代码：

#include<bits/stdc++.h>
using namespace std;
long long dp[100005],a[100005];
long long n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
    memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
		}
	}
	cout<<dp[n];
	return 0;
} 

i的初值可以改成2，这样更严谨，但这道题写1或2都可以过

for(int i=2;i<=n;i++){
		for(int j=1;j<=k;j++){
			dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
		}
	}