機器人到達指定位置的方法數問題
機器人到達指定位置的方法數問題
作者：Grey
原文地址：
題目描述
鏈接：//www.nowcoder.com/questionTerminal/54679e44604f44d48d1bcadb1fe6eb61
來源：牛客網
假設有排成一行的N個位置，記為1~N，開始時機器人在M位置，機器人可以往左或者往右走，如果機器人在1位置，那麼下一步機器人只能走到2位置，如果機器人在N位置，那麼下一步機器人只能走到N-1位置。規定機器人只能走k步，最終能來到P位置的方法有多少種。由於方案數可能比較大，所以答案需要對1e9+7取模。
暴力解
定義遞歸函數
long ways(int len, int start, int step, int end)
遞歸含義表示：機器人從坐標 start 開始，只能走 step 步，到達 end 的方法數是多少。
接下來是 base case，
if (step == 0) {
if (start == end) {
return 1L;
}
return 0L;
}
如果 step 只剩下 0 步，說明沒有步數可以走了，此時，如果 start == end ，表示正好就在目的地，返回一種方法數；
否則，返回 0 種方法數。
接下來是普遍情況，如果 start == 0，只能向右邊走，即: ways(len, start + 1, step - 1, end)；
如果 start == len - 1，只能向左邊走，即：ways(len, start - 1, step - 1, end)；
不在兩端位置，則既可以向左邊走，也可以向右邊走，即：(ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end))。
暴力解法完整程式碼如下
public static long ways(int len, int start, int step, int end) {
if (step == 0) {
if (start == end) {
return 1L;
}
return 0L;
}
// step不止一步
if (start == 0) {
return ways(len, start + 1, step - 1, end);
} else if (start == len - 1) {
return ways(len, start - 1, step - 1, end);
} else {
return (ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end));
}
}
超時
動態規劃-快取法（可 AC）
上述暴力遞歸過程，可變參數有兩個 start，step；可以設置一個二維數組 dp，用於快取遞歸中間過程的解，
long[][] dp = new long[len][step + 1];
dp[i][j]表示ways(len,i,j,end)的值，dp數組的值均初始化為 -1。
上述暴力遞歸過程增加這個 dp 參數，如果dp[i][j] != -1，則說明已經算過這個遞歸過程，直接返回dp[i][j]的值即可。
完整程式碼如下
public static long ways(int len, int start, int step, int end) {
long[][] dp = new long[len][step + 1];
for (int i = 0; i < len; i++) {
for (int j = 0; j <= step; j++) {
dp[i][j] = -1L;
}
}
dp(len, start, step, end, dp);
return dp[start][step];
}
private static long dp(int len, int start, int step, int end, long[][] dp) {
if (dp[start][step] != -1L) {
return dp[start][step] % MOD;
}
if (step == 0) {
dp[start][step] = start == end ? 1L : 0L;
return dp[start][step];
}
long ans;
// step不止一步
if (start == 0) {
ans = dp(len, start + 1, step - 1, end, dp);
} else if (start == len - 1) {
ans = dp(len, start - 1, step - 1, end, dp);
} else {
ans = (dp(len, start - 1, step - 1, end, dp) + dp(len, start + 1, step - 1, end, dp));
}
dp[start][step] = ans;
return ans;
}
動態規劃解-嚴格位置依賴（可 AC）
回到暴力遞歸解，偽程式碼如下
public static long ways(int len, int start, int step, int end) {
……
if (start == 0) {
return ways(len, start + 1, step - 1, end);
} else if (start == len - 1) {
return ways(len, start - 1, step - 1, end);
} else {
return (ways(len, start - 1, step - 1, end) + ways(len, start + 1, step - 1, end));
}
}
根據快取法得知，該遞歸過程使用一個二維數組 dp 即可存下所有結果，其中
dp[i][j]表示ways(len,i,j,end)的值，
通過觀察上述暴力遞歸過程，dp[i][j]依賴的位置是dp[i+1][j-1]，dp[i-1][j-1]，
所以，依據上述遞歸過程，可以改成嚴格位置的動態規劃版本，完整程式碼如下
public static long ways(int len, int start, int step, int end) {
long[][] dp = new long[len][step + 1];
// 填好第0列
dp[end][0] = 1L;
for (int j = 1; j < step + 1; j++) {
for (int i = 0; i < len; i++) {
if (i == 0) {
dp[i][j] = dp[1][j - 1];
} else if (i == len - 1) {
dp[i][j] = dp[len - 2][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] % MOD + dp[i + 1][j - 1] % MOD;
}
}
}
return dp[start][step];
}
動態規劃解-空間壓縮版（可 AC）
通過上述嚴格位置的動態規劃版本可以得知，dp[i][j]位置，依賴的位置是dp[i+1][j-1]，dp[i-1][j-1],
示例圖如下
而且，通過上述動態規劃解，可以得知第 0 列中，除了dp[end][0] = 1L，其餘都是 0，所以 dp 的第0列可以直接填充
所以，只需要用一個一維數組表示第 0 列，然後根據依賴關係，通過第 0 列推出第一列的值，一維數組此時表示第一列的值，依次這樣遞推下去，一直到最後一列，得解，這種方法就可以將二維數組壓縮成一維數組，節省了空間複雜度。
完整程式碼如下
public static long ways(int len, int start, int step, int end) {
long[] dp = new long[len];
dp[end] = 1L;
long tmp = 0;
for (int j = 1; j < step + 1; j++) {
for (int i = 0; i < len; i++) {
long ways = dp[i];
if (i == 0) {
dp[i] = dp[1] % MOD;
} else if (i == len - 1) {
dp[i] = tmp % MOD;
} else {
dp[i] = tmp % MOD + dp[i + 1] % MOD;
}
tmp = ways;
}
}
return dp[start];
}
