2022-10-03：给定一个正数 n，比如 6 表示数轴上有 0,1,2,3,4,5,6<0 或者 >6 的位置认为无法到达给定两个数字 x 和 y，0<= x，y <= n 表示小人一开始在 x 的位置，它的目的地是 y 的位置，比如 x = 1, y = 3 给定一个字符串 s，比如 : rrlrlr 任何一个 s 的子序列，对应着一种运动轨迹，r 表示向右，l 表示向左比如一开始小人在 1 位置，"rlr"是 s 的一个子序列那么运动轨迹是：1 -> 2 -> 1 -> 2 求，s 中有多少个字面值不同的子序列，能让小人从 x 走到 y，走的过程中完全不走出 0 到 n 的区域。比如，s = "rrlrlr", n = 6, x = 1, y = 3 有如下 5 个字面值不同的子序列 rr : 1 -> 2 -> 3rrlr : 1 -> 2 -> 3 -> 2 -> 3rrrl : 1 -> 2 -> 3 -> 4 -> 3rlrr : 1 -> 2 -> 1 -> 2 -> 3rrlrlr : 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 注意：一定要是字面值不同的子序列！相同字面值的子序列算一种，比如 s 中，有很多个 rr 的子序列，但是算一个，数据规模 : s 串长度 <= 1000, x,y,n <= 2500。来自 SnowFlake。
答案 2022-10-03：
动态规划。如果字符串长度为 m，位置数量 n。时间复杂度：O(m * n)。时间复杂度：O(n)。
代码用 rust 编写。代码如下：
use std::iter::repeat;fn main() { let ans = ways2("rrlrlr", 6, 1, 3); println!("ans = {}", ans);}
fn ways2(s: &str, n: i32, x: i32, y: i32) -> i32 { // all[i] : 让小人来到i位置的不同字面值的子序列数量 let mut all: Vec<i32> = repeat(0).take((n + 1) as usize).collect(); // r[i] : 让小人来到i位置的不同字面值，且以r字符结尾，的子序列数量 let mut r: Vec<i32> = repeat(0).take((n + 1) as usize).collect(); // l[i] : 让小人来到i位置的不同字面值，且以l字符结尾，的子序列数量 let mut l: Vec<i32> = repeat(0).take((n + 1) as usize).collect(); let mut add: Vec<i32> = repeat(0).take((n + 1) as usize).collect(); // 一开始小人在x，all[x] = 1, {} all[x as usize] = 1; // M for cha in s.bytes() { // 当前的指令字符串，cha if cha == 'r' as u8 { // 当前小人往右走 // 0 -> 1 // 1 -> 2 // 5 -> 6 // n-1 -> n // n -> 死 // 4 1000 // 5 +1000 // // 8 200 // 9 +200 for i in 0..n { // 9 方法数 新增 all[8] // 每一个新增方法，都还没有减去修正值呢！ add[(i + 1) as usize] += all[i as usize]; } for i in 0..=n { // 变了！成了纯新增！ add[i as usize] -= r[i as usize]; all[i as usize] += add[i as usize]; r[i as usize] += add[i as usize]; add[i as usize] = 0; } } else { // 遇到的是l // 当前小人往左走 // 0 左 死 // 1 0 // 2 1 // 3 2 for i in 1..=n { // 7 新增 之前8位置方法数 add[(i - 1) as usize] += all[i as usize]; } for i in 0..=n { // 修正，变成纯新增! add[i as usize] -= l[i as usize]; all[i as usize] += add[i as usize]; l[i as usize] += add[i as usize]; add[i as usize] = 0; } } } // 去重的！ return all[y as usize];}
复制代码
执行结果如下：
左神java代码
评论