個人覺得DP最煩的就是確定初始邊界，比如說這題，求10^9的數(shù)內各個數(shù)位相加的和中有多少個數(shù)的數(shù)位和等于S

初始條件：dp[0][j]=1 ? j=1、2…9

狀態(tài)轉移方程：

dp[i][j]表示：和為i，不超過j個數(shù)相加的符合條件的數(shù)有多少個

dp[i][j]=sum{dp[i-k][j-1] ?k=0、1…9}

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> using namespace std; int main() {int i,j,k,dp[89][30]={0},n;for(i=0;i<12;++i)dp[0][i]=1;for(i=1;i<82;++i)for(j=1;j<10;++j) //10^9，只需要算9位就好了for(k=0;k<10&&i-k>=0;++k) //k表示第j位為k {if(dp[i-k][j-1]) //如果前面的數(shù)位能組合成和i-kdp[i][j]+=dp[i-k][j-1];}while(~scanf("%d",&n)){if(n==1) //特判一下printf("10\n");else printf("%d\n",dp[n][9]);}return 0; }

?

轉載于:https://www.cnblogs.com/A-way/archive/2013/05/04/3059323.html

總結

以上是生活随笔為你收集整理的NYOJ_269_VF的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。