題目描述
學長有n個棒棒糖，他每次最多可以吃k個，請問他有多少種方法來吃棒棒糖
輸入
輸入兩個整數n， k（1 <= n <= 100000) （1 <= k <= 100）
輸出
一個正整數，為不同方法數，由于答案可能很大，你需要輸出對答案mod100003的結果，
樣例輸入
5 2
樣例輸出
8
提示
8種例子如下：
1-1-1-1-1
2-1-1-1
1-2-1-1
1-1-2-1
1-1-1-2
2-2-1
2-1-2
1-2-2
還是一道動態規劃的題，
dp[n]代表著n個棒棒糖時有幾種方式吃掉，
dp[n]的值是dp[n-1]到dp[n-k]的和，
假設當n=5，k=3時，dp[5]的值就是有4個棒棒糖時吃掉的方式+有3個棒棒糖時吃掉的方式+有2個棒棒糖時吃掉的方式，
#include <bits/stdc++.h>
using namespace std;
const int mod = 100003;
int dp[100005];
int main(){
memset(dp, 0, sizeof(dp));
int n, k;
cin >> n >> k;
int ans = 0;
dp[0] = 1;
for(int i = 1; i <= n; i++){
int num = 0;
for(int j = 1; j <= k; j++){
if(i-j < 0) break;
num = (num + dp[i-j]) % mod;
}
dp[i] = num;
}
cout << dp[n];
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235574.html
標籤：其他
上一篇：51單片機系列（三）51 單片機游戲設計 —— 雙人對戰小游戲（石頭剪刀布）
下一篇：sort函式自定義排序