京东笔试

三道编程题

小红有一个数组,她需要对效组操作n-1次,每次操作有两种选择: 1：选择数组的最后两个数,记x,y,将它们从数组中删除,然后将x＋y的个位数放到数组最后 2：选择数组的最后两个数,记x,y,将它们从数组中删除,然后将x*y的个位数放到数组最后 操作n-1步之后就剩一个数字，从0到9都有可能， 输出0-9可能的方案数

思路：动态规划，设计二维dp[i][j]表示第i次操作后，个位数为j的方案数，i从1到n，j取值0-9

理解题意相当于每次操作0-9的方案总数会*2

根据两种操作，动态规划递推式为

int op1 = (j + nums[n-i-1]) % 10;

int op2 = (j * nums[n-i-1]) % 10;

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

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

完整代码如下：

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

void solve(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<std::vector<int>> dp(n, std::vector<int>(10, 0));

    for (int i = 0; i < 10; ++i) {
        dp[0][i] = (i == nums[n-1]) ? 1 : 0;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 10; ++j) {
                int op1 = (j + nums[n-i-1]) % 10;
                int op2 = (j * nums[n-i-1]) % 10;
                dp[i][op1] += dp[i-1][j] % MOD;
                dp[i][op2] += dp[i-1][j] % MOD;
        }
    }
    for (int i = 0; i < 10; ++i) {
        std::cout<<dp[n-1][i]<<" ";
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }
    solve(nums);
    return 0;
}