DP 组合数的存储

题目

重述

1. 求解组合的数字根
2. 累计组合数（在这里用dp求解）

求解

1.数字根问题

根据他所给的例子，猜测： 每个数字%9，最后的和为数字根

注意：原来是%10 -> 现在是∑%9

原因未知，但这个操作，将会决定若你打开的是第9号门，由于我们中间的操作都是%9，所以这个数要从dp[n][0]处输出。

2.dp计算组合数

1.初始值的设定

这里在一开始的时候，要把所有人只有他自己的时候的对应开哪号门给计算出来。因为我们是以人为单位进行大循环，所以可以直接写在循环内部。

2.dp更新

两个循环

外面的大循环用来遍历所有的人

里面的小循环用来刷新所有的门

1）dp[i][a[i]+j] = dp[i]][a[i]+j] + dp[i-1][j] 代表选择加上这个数进行刷新

2）dp[i][j] = dp[i][j] + dp[i-1][j] 代表不加上这个数进行刷新

最后所有的数刷新至dp[n][0-9]中

代码

c++

#define mod 998244353
using namespace std;
typedef long long ll;
ll num[100100] = {0};
ll dp[100100][10] = {0};
int main(void){
	ll n;
	cin >> n;
	ll num[n];
	for(int i=0; i<n; i++){
		cin >> num[i];
	}
	//ll dp[n][9] = {0};
	//dp[0][0] = 1;
	for(int i=0; i<n; i++){
		dp[i][num[i]%9] = (dp[i][num[i]%9] + 1) % mod;		
		for(int j=0; j<9; j++){
			dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
			dp[i][(num[i]+j)%9] = (dp[i][(num[i]+j)%9] + dp[i-1][j]) % mod;
		}
	}
	for(int i=1; i<9; i++){
		cout << dp[n-1][i] << " ";
	}
	cout << dp[n-1][0];
} 

python

n = int(input())
## 读入长串
num = list(map(int, input().split(" ")))
## 初始化二维数组
dp = [[0 for i in range(0, 10)]for j in range(0, 100005)]

for i in range(0, n):
	dp[i][num[i] % 9] = (dp[i][num[i] % 9] + 1) % mod
	for j in range(0, 9):
		dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
		dp[i][(num[i]+j) % 9] = (dp[i][(num[i]+j) % 9] + dp[i-1][j]) % mod

for i in range(1, 9):
	print(dp[n-1][i], end=" ")

print(dp[n-1][0])