Count ways to reach end from start stone and come back, without taking using the same stone twice with at most K jumps at each step

huangapple go评论106阅读模式
英文:

Count ways to reach end from start stone and come back, without taking using the same stone twice with at most K jumps at each step

问题

以下是你的代码的中文翻译部分:

n = 5000
k = 400
dp = [[0]*(n+1) for _ in range(n+1)]
dp[1][1] = 1

start_time = time.time()

for i in range(2, n+1):
    total = 0
    for j in range(i-k, i):
        dp[j][i] = dp[j][j]
        total += dp[j][i]
    dp[i][i] = total

end_time = time.time()

print(dp[-1][-1] % 998244353)

这是用于计算从加拿大到美国的路径的代码部分,但如何计算从美国返回到加拿大的路径呢?

英文:

Richard is a penguin who regularly commutes between Canada and the United States.

Specifically, Canada is at location 1
, and the United States is at location N.
In locations 2 through N, there are ice blocks that Richard can jump on. Richard can jump from location i to location j if and only if abs(i-j)<=k.

Richard does not believe in wasting time, so when he is commuting in one direction, he will always move in that direction. This means that when commuting from Canada to the United States, locations are monotonically increasing in number, and when commuting from the United States to Canada, locations are monotonically decreasing in number.

Richard's commute is complicated during the fall and spring when the ice is thawing between Canada and the United States. If Richard jumps on an ice block, that ice block will melt enough that it will not be usable on the return journey.

Count the number of distinct ways that Richard can do a round-trip commute from Canada to the United States and back. Two ways are distinct if, in some direction, Richard uses an ice block travelling in that direction in one way but not in the other way.

2<=k<=N<=5000

sample input:
5 3
sample output
12

how should i approach this problem?

n = 5000
k = 400
dp = [[0]*(n+1) for _ in range(n+1)]
dp[1][1] = 1

start_time = time.time()

for i in range(2, n+1):
    total = 0
    for j in range(i-k, i):
        dp[j][i] = dp[j][j]
        total += dp[j][i]
    dp[i][i] = total

end_time = time.time()


print(dp[-1][-1] % 998244353)

here is my code for calculating the way there, but what about the way back?your text

答案1

得分: 4

想象一下给第2到N-1号石头上色。如果它们在从加拿大到美国的路上使用,则将它们涂成红色,如果它们在回程路上使用,则将它们涂成蓝色。如果它们根本没有被使用,则保持它们为灰色。你的问题是有多少种方式可以上色这些石头,以确保没有>= k 个非红色石头或非蓝色石头的间隙。

制作一个包含上色石头方式数量的矩阵DP[r][b],其中最高的红色石头是r,最高的蓝色石头是b,并且没有非法的红色间隙<r或蓝色间隙<b。

如果按照r+b、max(r,b)等递增的顺序填充矩阵,那么每个元素可以从之前填充的元素中以O(k)的时间计算出来。然后,根据已填充的矩阵,你的最终答案可以在O(k^2)的时间内计算出来。

由于矩阵的大小为(N-2)^2,所以这需要O(kN^2)的时间。

英文:

Imagine coloring rocks 2 through N-1. Color them red if they're used on the way from Canada to the US, and color them blue if they're used on the way back. Leave them gray if they are not used at all. Your question is how many ways you can color the rocks such that there are no gaps of >= k non-red stones or non-blue stones.

Make a matrix DP[r][b] that contains the number of ways to color the stones such that the highest red stone is r, the highest blue stone is b, and there are no illegal red gaps < r or blue gaps < b.

If you fill out the matrix in order of increasing r+b, max(r,b), etc., then each element can be calculated in O(k) time from previously filled out elements. Then your final answer can be computed in O(k<sup>2</sup>) time given the filled out matrix.

Since the matrix has size (N-2)<sup>2</sup>, this takes O(kN<sup>2</sup>) time.

答案2

得分: 0

这似乎适用于你在描述中提到的示例。也许你可以添加更多示例?

JavasScript 代码:

function f(n, k) {
  dp = {};

  function g(i, lastS, lastN) {
    if (i == n) {
      return 1;
    }

    const key = String([i, lastS, lastN]);

    if (key in dp) {
      return dp[key];
    }

    let result = 0;

    if (i - lastS < k && i - lastN < k) {
      result += g(i + 1, lastS, lastN);
    }

    if (i - lastN < k) {
      result += g(i + 1, i, lastN);
    }

    if (i - lastS < k) {
      result += g(i + 1, lastS, i);
    }

    return dp[key] = result;
  }

  return g(2, 1, 1);
}

var inputs = [
  [5, 3], // 12
  [3, 2] // 3
];

for (const [n, k] of inputs) {
  console.log(`(${ n }, ${ k }) -> ${ f(n, k) }`);
}

请注意,这段代码是使用 JavaScript 编写的。

英文:

This seems to work for the example you have in the description. Maybe you could add more examples?

JavasScript code:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function f(n, k) {
  dp = {};

  function g(i, lastS, lastN) {
    if (i == n) {
      return 1;
    }
    
    const key = String([i, lastS, lastN]);
    
    if (key in dp) {
      return dp[key];
    }
    
    let result = 0;
    
    if (i - lastS &lt; k &amp;&amp; i - lastN &lt; k) {
      result += g(i + 1, lastS, lastN);
    }
 
    if (i - lastN &lt; k) {
      result += g(i + 1, i, lastN);
    }
    
    if (i - lastS &lt; k) {
      result += g(i + 1, lastS, i);
    }
  
    return dp[key] = result;
  }
  
  return g(2, 1, 1);
}

var inputs = [
  [5, 3], // 12
  [3, 2] // 3
];

for (const [n, k] of inputs) {
  console.log(`(${ n }, ${ k }) -&gt; ${ f(n, k) }`);
}

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年8月9日 12:15:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/76864533-2.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定