NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 20 题

阅读程序写结果:

#include <iostream>
using namespace std;
int n, m;

int findans(int n, int m) {
    if (n == 0) return m;
    if (m == 0) return n % 3;
    return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}

int main(){
    cin >> n >> m;
    cout << findans(n, m) << endl;
    return 0;
}

输入：5 6

看到递归式 f(n,m)=f(n-1,m)-f(n,m-1)+f(n-1,m-1) → 先画二维表，按行从左到右填。

中间是减号，算出负数（如 f(2,1)=-1）正常；边界 m=0 时是取余 n%3，勿看成 n/3。

考点：递归与递推｜二维填表（动态规划雏形）

程序在做什么

输入 n,m，递归计算 f(n,m) = f(n-1,m) - f(n,m-1) + f(n-1,m-1)，边界 f(0,m)=m，f(n,0)=n%3。