本人是个刚接触算法题的小白，写这篇文章是因为题解中的大佬写的文章对于刚接触 算法的小白来说有点晦涩难懂，我在最开始看这道题的时候看了好久大佬的题解才慢慢 理解了大佬的思路（😂），为了帮助更多和我一样的小白更好的理解这些题的解题思路 写了这篇文章，后面的内容如有错
展开全文
简单说下题意，给定一个数字串，问有多少的子串可以被3整除。 首先一个数如果可以被3整除，那么这个数各位和一定可以被3整除。所以这个题应该是线性dp，我们定义dp[i][j]为前i个中整除3余数为j（只有0，1，2三个数）的个数，然后从头到尾线性dp一遍就可以了。 下面看一下代码：
展开全文
闫氏dp分析法 1、状态表示：指的是，以结尾的对3取余后值为j的集合2、 方案数3、集合划分：每次转移都是从 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm&g
展开全文
动态规划的问题。想了好久终明白了，先写下来自己看了别人后的理解，免得以后又忘记了。 思路：整体的思路就是，把输入的数字按顺序放到一个数组里面，然后每次依次加入一个数字。举一个例子，512。 1、这时数组arr中的数据为5、1、2。然后进行循环。先进行第一次循环，先处理数字5。因为5对3取模的结果为2
展开全文
非曰能，但好学。欢迎一起交流学习 问题分析 动态规划问题，定义好动态变量则成功了一半，找到变量的迭代关系怎成功一大半。 动态变量 变量定义，在adoptions的题解已经提及,引用如下 我们定义dp[i][j]为前i个中整除3余数为j（只有0，1，2三个数）的个数 我再啰嗦得解释一下，dp[i]
展开全文
首先，定义状态：设 dpi,jdp_{i,j}dpi,j 表示数字串前 iii 个数字的子序列中，模3余 jjj 的子序列个数。
然后，定义状态转移方程：设 sis_isi 表示数字串中第 iii 个数字，则状态转移方程为：
dpi,j=dpi−1,j+dpi−1,(j−si mod 3+3)
展开全文
思路
dfs的数据范围只能出到20左右吧，这道题肯定是要用记忆化思想的。
我们先处理一下每一位数字，将他们都模3，然后我们知道一个数能被3整除，那么每一位加起来就是3的倍数。
因此我们dp[i][j]表示前i位数字%3余数为j的方案数。首先我们子序列不选第i位必有dp[i][j]=dp[i-1][j
展开全文
被3整除的子序列
[小菜鸡第一次写题解，请多多指教]
3的倍数特点：所有数位数字之和是3的倍数。
算法思路：二维dp
集合表示：f[i][j]表示长度为i的字符串中除以3后余数为j
集合含义：f[i][j]表示子串的个数
状态转换：将集合划分为两部分，第一部分为a[i]（第i个元素）除以
展开全文
dp[0][(a[0]-'0')%3]=1;
for(int i=1;i<len;i++){
int x=(a[i]-'0')%3;
dp[i][x]=(dp[i][x]+1)%mod;
for(int j=0;j<3;j++){
展开全文
楼上的大佬们已经把解析说得很详细了，我利用(a==b)的返回值把状态方程优化了一下。 #include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int dp[55][3]
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
