动态规划初识

动态规划初识

适合用动态规划的问题特征：可以分解成相互重叠的若干子问题； 满足最优性原理（结构性质）：该问题的最优解中也包含着其子问题的最优解。一般地，子问题的联系体现在某种递推关系，通过这种递推计算可以把问题的解存储起来，后期直接使用，避免重复运算。

简单的dp例子：​​#includeusing namespace std;int main(){ int i,j,m[20][20],n; for(i=1;i<16;i++){ m[i][0]=1; m[0][i]=1; } for(i=1;i<16;i++){ for(j=1;j<16;j++){ m[i][j] = m[i-1][j]+m[i][j-1]; } } while(cin>>n&&n){ printf("%d\n",m[n][n]); } return 0;}

再来一个：

​​#includeusing namespace std;const int maxn=5e5+5;bool judge[maxn*100]; //估计的大小，标记数组int number[maxn];int main(){ int i,k; judge[0]=1; number[0]=0; for(i=1;i0&&judge[t]==0){ number[i]=t; judge[t]=1; } else { number[i]=number[i-1]+i; judge[number[i]]=1; } } while(cin>>k&&k!=-1){ printf("%d\n",number[k]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。