题目：
四个参数N表示行走范围，M 表示起点，k表示步数，p表示目标位置，计算出从M 点出发，经过K步之后到达P点有几种方法
机器人在1点和N 点只能向中间走，机器人在除了两端的任意位置都可以自由选择向左或向右走
分析：
题目已经很明确，一共可以分为三种情况
在1点 只能往2 点走，计算出所有方法数
在n点，只能往n-1点走，计算出所有方法数
在任意n点，可以往n+1或n-1 走，计算出两种方案所有方法数，然后相加
代码：
package main
import(
"fmt"
// "math"
// "strconv"
)
//cur==m 当前位置 rest==k剩余几步
func walk(n,cur,rest,p int) int{
if rest ==0{
if cur==p{
return 1
}
return 0
}
if cur==1{
return walk(n,2,rest-1,p)
}
if cur==n{
return walk(n,n-1,rest-1,p)
}
return walk(n,cur+1,rest-1,p)+walk(n,cur-1,rest-1,p)
}
// n 范围 m起始位置 k 需要走k步 p目标位置
func way(n,m,k,p int)int {
if n<2 || k<1 ||m<1 || m>n || p<1 || p>n{
return 0
}
return walk(n,m,k,p)
}
func main(){
fmt.Println(way(7,3,2,3))
}
加上缓存：
package main
import(
"fmt"
// "math"
// "strconv"
)
//cur==m 当前位置 rest==k剩余几步
func walk(n,cur,rest,p int,dp [][]int) int{
if dp[cur][rest]!=-1{
return dp[cur][rest]
}
if rest ==0{
if cur==p{
dp[cur][rest]=1
return dp[cur][rest]
}
return 0
}
if cur==1{
dp[cur][rest]= walk(n,2,rest-1,p,dp)
return dp[cur][rest]
}
if cur==n{
dp[cur][rest]= walk(n,n-1,rest-1,p,dp)
return dp[cur][rest]
}
dp[cur][rest]= walk(n,cur+1,rest-1,p,dp)+walk(n,cur-1,rest-1,p,dp)
return dp[cur][rest]
}
// n 范围 m起始位置 k 需要走k步 p目标位置
func way(n,m,k,p int)int {
if n<2 || k<1 ||m<1 || m>n || p<1 || p>n{
return 0
}
dp:=[][]int{}
for i:=0;i
tmp:=[]int{}
for j:=0;j
tmp=append(tmp,-1)
}
dp=append(dp,tmp)
}
return walk(n,m,k,p,dp)
}
func main(){
fmt.Println(way(70,30,20,30))
}
动态规划：
package main
import(
"fmt"
// "math"
// "strconv"
)
//cur==m 当前位置 rest==k剩余几步
func walk(n,cur,rest,p int,dp [][]int) int{
if dp[cur][rest]!=-1{
return dp[cur][rest]
}
if rest ==0{
if cur==p{
dp[cur][rest]=1
return dp[cur][rest]
}
return 0
}
if cur==1{
dp[cur][rest]= walk(n,2,rest-1,p,dp)
return dp[cur][rest]
}
if cur==n{
dp[cur][rest]= walk(n,n-1,rest-1,p,dp)
return dp[cur][rest]
}
dp[cur][rest]= walk(n,cur+1,rest-1,p,dp)+walk(n,cur-1,rest-1,p,dp)
return dp[cur][rest]
}
// n 范围 m起始位置 k 需要走k步 p目标位置
func way(n,m,k,p int)int {
if n<2 || k<1 ||m<1 || m>n || p<1 || p>n{
return 0
}
dp:=[][]int{}
for i:=0;i
tmp:=[]int{}
for j:=0;j
tmp=append(tmp,-1)
}
dp=append(dp,tmp)
}
return walk(n,m,k,p,dp)
}
func process1(n,m,k,p int) int{
dp:=[][]int{}
for i:=0;i
tmp:=[]int{}
for j:=0;j
tmp=append(tmp,0)
}
dp=append(dp,tmp)
}
// 第一行初始化为0，它的实际值也为0，因此不用再处理
//第一列只有当cur=p的时候为1，其他也为0 不用处理
dp[p][0]=1
for j:=1;j
dp[1][j]=dp[2][j-1]
}
//有数据的依赖关系，每一个格子数据依赖左上和左下位置，所以一列一列来填（按行来填的话拿不到左下位置）
// 一般情况取左上和左下的和
//最后一行因为dp初始化的时候多加了一行，这样i+1就不会越界，而且最后一行因为左上有值，左下为0，相加就相当于等于左上，符合规则，因此也不用再处理
for j:=1;j<=k;j++{
for i:=1;i<=n;i++{
dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1]
}
}
for i:=0;i
fmt.Println(dp[i])
}
fmt.Println(dp[m][k])
return dp[m][k]
}
func main(){
// fmt.Println(way(7,2,5,3))
process1(7,2,5,3)
}
总结：
1 由数据的依赖关系，每一个格子数据依赖左上和左下位置，所以一列一列来填（按行来填的话拿不到左下位置）
2 最后一行因为dp初始化的时候多加了一行，这样i+1就不会越界，而且最后一行因为左上有值，左下为0，相加就相当于等于左上，符合规则，因此也不用再处理
