[算法]美团春招笔试题C-求有趣子序列数(DP)

题目

输入n，以及长度为n的数组元素

输出数组的非空子序列中有多少个“有趣序列”mod 998244353，有趣序列指所有元素满足arr[i]%i == 0， i从0记。

例：

输入：

2

1 3

输出：

2

题解

DP
状态：dp[i][j] = new long[arr.length()+1][arr.length()]表示子数组arr[0]到arr[j]有多少个长度为i的有趣序列
伪代码

for(j from 1 to j-1){

    for(i from 1 to j){

        dp[i][j]=dp[i-1][j-1]+dp[i][j-1]，当arr[j]%i ==0;

        dp[i][j]=dp[i-1][j-1]，当arr[j]%i!=0;

    }

}

最终所求为对dp[i][arr.length()-1]，i from 1 to arr.length() 求和。
上述状态转移方程可以使用滚动数组降低空间复杂度，即
- 状态：dp[i][j] = new long[arr.length()+1][2]
- 伪代码

for(j from 1 to j-1){

     for(i from 1 to j){

        if(j==1) {

          dp[i][j]=dp[i-1][0]+dp[i][0]，当arr[j]%i ==0;

          dp[i][j]=dp[i-1][0]，当arr[j]%i!=0;

        }

        if(j==0){

         dp[i][j]=dp[i-1][1]+dp[i][1]，当arr[j]%i ==0;

         dp[i][j]=dp[i-1][1]，当arr[j]%i!=0;

        }

    }

}

代码

package Exam;

import java.util.Scanner;

public class MeiTuanC {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0;i < arr.length; ++i){

            arr[i] = sc.nextInt();

        }

        long[][] cnt = new long[n+1][2];//滚动数组

        cnt[0][0] = 1;

        cnt[1][0] = 1;

        cnt[0][1] = 1;

        int j = 0;

        for(int i = 1 ;i < arr.length; ++i){//序列尾元素idx

            j = (j + 1) % 2;

            for(int len = 1;len <= i + 1;++len){//子序列长度

                int preJ = (j + 1) % 2;

                if(arr[i] % len!=0){

                    cnt[len][j] = cnt[len][preJ];

                }else{

                    cnt[len][j] = (cnt[len - 1][preJ] + cnt[len][preJ]) % 998244353;

                }

            }

        }

        long sum =0;

        for(int i = 1;i <= arr.length; ++i){

            sum += (cnt[i][j]) % 998244353;

        }

        sum %= 998244353;

        System.out.print(sum);

    }

}

巴特西

[算法]美团春招笔试题C-求有趣子序列数(DP)

题目

题解

相关

代码

最新文章

热门文章