算法学习之动态规划

递推题目1.
牛牛与数组

dp[i][j]表示数组长度为n时，以 j 结尾的数组个数;
递推方程
dp[i][j] = sum_{j = 1}^{n}(dp[i-1][j]) - sum_{k = j}^{k}(dp[i-1][k]); 其中k是 j 的倍数;

/*
刷新数组和每一个数刷新前边所有的子序列的和
*/
#include <iostream>
#include<stdio.h>
using namespace std;

const int MAXN = 100001;
const int MOD = 1000000007;
int sum[11][MAXN];
int ans = 0;
int main()
{
    int n,k,sumt;
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= k;i++)sum[1][i] = 1;
    for(int i = 2; i <= n;i++){
        sumt = 0;
        for(int j = 1;j <= k;j++)sumt = (sum[i-1][j] + sumt) % MOD;
        for(int j = 1;j <= k;j++){
            int sum1 = 0;
            for(int kk = j * 2;kk <= k;kk += j)
                sum1 = (sum[i-1][kk] + sum1) % MOD;
            sum[i][j] = (sumt - sum1) % MOD;
        }
    }
    for(int i = 1;i <= k;i++)ans = (ans + sum[n][i]) % MOD;
    printf("%d\n",ans);
}

递推题目二
被三整除的子序列

两个技巧
能整除三子序列的和是3的倍数
子序列和对三取余有三种情况，0，1，2

a[i]：表示前面所有子序列中和为 i 的子序列个数
sum[i] :表示现在和是 i 的子序列中和为 i 的子序列个数i = 0,1,2
递推式是：sum[(i + x) % 3] += a[i];

#include <iostream>
#include<stdio.h>
using namespace std;

const int  MOD = 1000000007;
int sum[3],a[3],ans = 0;
int main()
{
    string s;
    cin>>s;
    for(int i = 0;i < s.length();i++){
        int x = (int)(s[i] - '0');
        for(int j = 0;j < 3;j++)a[j] = sum[j];
        for(int j = 0;j < 3;j++)
            sum[(x + j) % 3] = (sum[(x + j) % 3] + a[j]) % MOD;
        sum[x % 3] = (sum[x % 3] + 1) % MOD;
    }
    cout<<sum[0]<<endl;
}