# 每天一道动态规划——第一天

``````动态规划一定要去尝试！
``````

# 题目一：

## 1）题目描述

``````1 2 3 4 5 6
N=6|cur=2|aim=3|res=3

``````

## 2）代码

``````public class demo01 {

public static void main(String[] args) {
int res = 13;
int cur = 2;
int aim = 3;
int N = 7;

int result = 0;

result = process1(cur, aim, res, N);
System.out.println(result);

int[][] dp = new int[N + 1][res + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= res; j++) {
dp[i][j] = -1;
}
}
int result2=process2(cur, aim, res, N,dp);
System.out.println(result2);
}

public static int process1(int cur, int aim, int res, int N) {
/*
cur:当前位置
aim:目标位置
res:剩余步数
N：共有哪些位置
*/
if (res == 0) {
return cur == aim ? 1 : 0;
}
if (cur == 1) {
return process1(2, aim, res - 1, N);
} else if (cur == N) {
return process1(N - 1, aim, res - 1, N);
} else {
return process1(cur - 1, aim, res - 1, N) + process1(cur + 1, aim, res - 1, N);
}

}
}
``````

## 3）代码优化

cur的范围为：1~N
res的范围为：0~K

-1为没计算过；
!=-1为计算过；—有缓存先走缓存

``````package com.sq.demo72DynamicPlan;

public class demo01 {
static int res = 3;
static int cur = 2;
static int aim = 3;
static int N = 7;

public static void main(String[] args) {

long start = System.nanoTime();
int[][] dp = new int[N + 1][res + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= res; j++) {
dp[i][j] = -1;
}
}
int result2 = process2(cur, aim, res, N, dp);
long end = System.nanoTime();
System.out.println(result2);
System.out.println(end - start);

}

public static int process2(int cur, int aim, int res, int N, int[][] dp) {
/*
cur:当前位置
aim:目标位置
res:剩余步数
N：共有哪些位置
*/

if (dp[cur][res] != -1) {
return dp[cur][res];
}

int ans = 0;
if (res == 0) {
ans = (cur == aim ? 1 : 0);
} else if (cur == 1) {
ans = process2(2, aim, res - 1, N, dp);
} else if (cur == N) {
ans = process2(N - 1, aim, res - 1, N, dp);
} else {
ans = process2(cur - 1, aim, res - 1, N, dp) + process2(cur + 1, aim, res - 1, N, dp);
}
dp[cur][res] = ans;
return ans;

}
}
``````

## 4）代码优化2

``````	1 2 3 4 5
N=5|cur=2|aim=4|res=6
``````

``````public class demo03 {

static int res = 23;
static int cur = 2;
static int aim = 3;
static int N = 7;

public static void main(String[] args) {
ways3(cur, aim, res, N);

}

public static void ways3(int cur, int aim, int res, int N) {

System.out.println("第三种方式");
long start = System.nanoTime();
int[][] dp = new int[N + 1][res + 1];

//第0列是初始条件
dp[aim][0] = 1;//第0列其余的位置都是0

for (int i = 1; i <= res; i++) {
dp[1][i] = dp[2][i - 1];
for (int j = 2; j < N; j++) {
dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
}
dp[N][i] = dp[N - 1][i - 1];
}
long end = System.nanoTime();
System.out.println("共有方式："+dp[cur][res]+"种");
System.out.println("耗时为(ns):"+(end-start));
}
}
``````

THE END