2023-12-13：用go语言，密码是一串长度为n的小写字母，一则关于密码的线索纸条， 首先将字母a到z编号为0到25编号，

2023-12-13：用go语言，密码是一串长度为n的小写字母，一则关于密码的线索纸条，

首先将字母a到z编号为0到25编号，

纸条上共有n个整数ai，其中a1表示密码里第一个字母的编号，

若i>1的话就表示第i个字母和第i-1个字母编号的差值，

例如，a2就代表密码中第1个字母和第2个字母编号的差值，

若密码是acb，那么纸条上的数字就是[5, 2, 1]，

a b c d e f

返回可能的密码的个数，由于结果可能很大，

1

0

来自字节。

答案2023-12-13：

灵捷3.5

大体过程如下：

算法一（ways1）：

1.定义函数ways1，传入一个整数数组arr作为参数。

2.在process1函数中，传入当前索引i和前一个字母的编号pre作为参数。

3.如果pre小于0或大于25，则返回0；否则，进入下一步。

4.若当前索引i等于数组长度，则说明已经遍历完所有字母，返回1。

5.否则，定义变量ans初始化为0。

6.递归调用process1函数，传入i+1和pre-arr[i]作为参数，并将结果累加到ans上。

7.递归调用process1函数，传入i+1和pre+arr[i]作为参数，并将结果累加到ans上。

8.返回ans作为结果。

算法二（ways2）：

1.定义函数ways2，传入一个整数数组arr作为参数。

2.初始化变量mod为1000000007和n为数组长度。

3.创建二维切片dp，大小为(n+1)×26，用于存储动态规划的结果。其中dp[i][j]表示考虑第i个位置时，以j号字母结尾的可能密码的个数。

4.将最后一行dp[n][j]全部初始化为1，表示在最后一个位置时，每个字母都是合法的密码结尾位置。

5.倒序遍历数组arr中的元素：

5.1.对于每个字母对应的编号j，遍历0到25：

5.1.1.如果j-arr[i]大于等于0，则将dp[i][j]的值更新为dp[i+1][j-arr[i]]。

5.1.2.如果j+arr[i]小于26，则将dp[i][j]的值与dp[i+1][j+arr[i]]相加，并对mod取模。

6.返回dp[1][arr[0]]作为结果。

算法一的时间复杂度是O(2^n)，空间复杂度是O(n)。

算法二的时间复杂度是O(n)，空间复杂度是O(n)。

go完整代码如下：

package main

import "fmt"

func ways1(arr []int) int {

return process1(arr, 1, arr[0])

}

func process1(arr []int, i, pre int) int {

if pre  25 {

return 0

} else {

if i == len(arr) {

return 1

} else {

ans := 0

ans += process1(arr, i+1, pre-arr[i])

ans += process1(arr, i+1, pre+arr[i])

return ans

}

}

}

func ways2(arr []int) int {

mod := 1000000007

n := len(arr)

dp := make([][]int, n+1)

for i := 0; i 

dp[i] = make([]int, 26)

}

for j := 0; j 

dp[n][j] = 1

}

for i := n - 1; i >= 1; i-- {

for j := 0; j 

if j-arr[i] >= 0 {

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

}

if j+arr[i] 

dp[i][j] = (dp[i][j] + dp[i+1][j+arr[i]]) % mod

}

}

}

return dp[1][arr[0]]

}

func main() {

arr := []int{5, 2, 1}

result1 := ways1(arr)

result2 := ways2(arr)

fmt.Println("Result using ways1:", result1)

fmt.Println("Result using ways2:", result2)

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

int process1(std::vector& arr, int i, int pre) {

if (pre  25) {

return 0;

}

else {

if (i == arr.size()) {

return 1;

}

else {

int ans = 0;

ans += process1(arr, i + 1, pre - arr[i]);

ans += process1(arr, i + 1, pre + arr[i]);

return ans;

}

}

}

int ways1(std::vector& arr) {

return process1(arr, 1, arr[0]);

}

int ways2(std::vector& arr) {

const int MOD = 1000000007;

int n = arr.size();

std::vector dp(n + 1, std::vector(26));

for (int j = 0; j 

dp[n][j] = 1;

}

for (int i = n - 1; i >= 1; --i) {

for (int j = 0; j 

if (j - arr[i] >= 0) {

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

}

if (j + arr[i] 

dp[i][j] = (dp[i][j] + dp[i + 1][j + arr[i]]) % MOD;

}

}

}

return dp[1][arr[0]];

}

int main() {

std::vector arr{ 5, 2, 1 };

int result1 = ways1(arr);

int result2 = ways2(arr);

std::cout 

std::cout 

return 0;

}

在这里插入图片描述c完整代码如下：

#include 

#include 

int process1(int* arr, int i, int pre, int len) {

if (pre  25) {

return 0;

}

else {

if (i == len) {

return 1;

}

else {

int ans = 0;

ans += process1(arr, i + 1, pre - arr[i], len);

ans += process1(arr, i + 1, pre + arr[i], len);

return ans;

}

}

}

int ways1(int* arr, int len) {

return process1(arr, 1, arr[0], len);

}

int ways2(int* arr, int len) {

const int MOD = 1000000007;

int n = len;

int** dp = (int**)malloc((n + 1) * sizeof(int*));

for (int i = 0; i 

dp[i] = (int*)malloc(26 * sizeof(int));

}

for (int j = 0; j 

dp[n][j] = 1;

}

for (int i = n - 1; i >= 1; --i) {

for (int j = 0; j 

if (j - arr[i] >= 0) {

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

}

if (j + arr[i] 

dp[i][j] = (dp[i][j] + dp[i + 1][j + arr[i]]) % MOD;

}

}

}

int result = dp[1][arr[0]];

for (int i = 0; i 

free(dp[i]);

}

free(dp);

return result;

}

int main() {

int arr[] = { 5, 2, 1 };

int len = sizeof(arr) / sizeof(arr[0]);

int result1 = ways1(arr, len);

int result2 = ways2(arr, len);

printf("Result using ways1: %d\n", result1);

printf("Result using ways2: %d\n", result2);

return 0;

}

在这里插入图片描述