描述
在物质位面“现实”中，有n+1个星球，分别为星球0，星球1，……，星球n。
每一个星球都有一个传送门，通过传送门可以直接到达目标星球而不经过其他的星球。
不过传送门有两个缺点。
第一，从星球i通过传送门只能到达编号比i大，且与i的差不超过limit的星球。
第二，通过传送门到达星球j，需要cost[j]个金币。
现在，流浪剑客斯温到达星球0后身上有m个金币，请问他有多少种方法通过传送门到达星球n？
- 1 <= n <= 50, 0 <= m <= 100, 1 <= limit <= 50, 0 <= cost[i] <= 100。
- 由于cost[0]没有意义，题目保证cost[0] = 0。
在线评测地址：领扣题库官网
样例1
比如 n = 15, 返回一个字符串数组：
输入:
n = 1
m = 1,
limit = 1
cost = [0, 1]
输出:
1解释:
方案1：星球0→星球1
样例2
输入:
n = 1
m = 1
limit = 1
cost = [0,2]
输出:
0解释:
无合法方案
算法：dp
我们用dpidpi代表从星球00出发到达星球ii后拥有jj个金币的方案数。
- 设置初始状态为在第0号星球，此时拥有m个币。dp0=1dp0=1。
- 我们考虑dpidpi的前继状态，可以发现，所有编号比i小，且差在limit之内的都能转移过来，并且转移过程消耗cost[i]cost[i]的币，所以对它的前继状态的方案数累加。
- 可列出状态转移方程如下所示，
- 最后因为要求总方案数，对于sven在第nn号星球的所有剩余金币数量求和即可。答案
复杂度分析
- 时间复杂度O(n∗m∗limit)O(n∗m∗limit)
空间复杂度O(n∗m)O(n∗m)
- 就是dpi所有的状态数
public class Solution {
/**
* @param n: the max identifier of planet.
* @param m: gold coins that Sven has.
* @param limit: the max difference.
* @param cost: the number of gold coins that reaching the planet j through the portal costs.
* @return: return the number of ways he can reach the planet n through the portal.
*/
public long getNumberOfWays(int n, int m, int limit, int[] cost) {
//
long[][] dp = new long[n + 1][m + 1];
for (int i = 0; i < m; i++) {
dp[0][i] = 0;
}
dp[0][m] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
for (int t = Math.max(0, i - limit); t <= i - 1; t++) {
if (j + cost[i] <= m) {
dp[i][j] += dp[t][j + cost[i]];
}
}
}
}
long ans = 0;
for (int i = 0; i <= m; i++) {
ans += dp[n][i];
}
return ans;
}
}
