[程序员代码面试指南]递归和动态规划-机器人达到指定位置方法数(一维DP待做)（DP）

题目描述

一行N个位置1到N，机器人初始位置M，机器人可以往左/右走（只能在位置范围内），规定机器人必须走K步，最终到位置P。输入这四个参数，输出机器人可以走的方法数。

解题思路

DP

方法一：时间复杂度O(NK),空间复杂度O(NK)

方法二：时间复杂度O(NK),空间复杂度O(N)

方法一代码

public class Solution {

	//ans=walk(N,M,K,P);

	public int walk(int N,int cur,int rest,int P) {

			int[][] dp=new int[rest+1][N+1];

			for(int i=1;i<=N;++i) {

				if(i==P) {dp[0][i]=1;}

				else {

					dp[0][i]=0;

				}

			}

			for(int i=1;i<=rest;++i) {

				for(int j=1;j<=N;++j) {

					if(j==1) {

						dp[i][j]=dp[i-1][j+1];

					}

					else if(j==N) {

						dp[i][j]=dp[i-1][j-1];

					}

					else {

						dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];

					}

				}

			}

			return dp[rest][cur];

		}

}

巴特西

[程序员代码面试指南]递归和动态规划-机器人达到指定位置方法数(一维DP待做)（DP）

题目描述

解题思路

方法一代码

最新文章

热门文章