PAT B1001 害死人不偿命的(3n+1)猜想
卡拉兹(Callatz)猜想：
对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学
...
最长不下降子序列
在一个数字序列中，找到一个最长的子序列(可以不连续)，使得这个子序列是不下降(非递减)的。
分析：此题如若采用暴力的方法来解答，即对于每个元素有取或是不取两种选择，时间复杂度可以达到O(2^n)。
令dp[i]表示以A[i]结尾的最长不下降子序列长度(和最大连续子序列和问题一样，以A[i]结尾是强制
...
最大连续子序列的和
给定一个数字序列A1，A2，…，An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大的和。
分析：这个问题如若暴力来做，枚举i,j需要O(n^2)的复杂度，而计算A[i]+…+A[j]需要O(n)的复杂度，因此总的复杂度为O(n^3)。就算采用记录前缀和的方
...
动态规划
1、动态规划的递归写法(记忆化搜索)：重点在于如何记录子问题的解，从而避免下次遇到同样的子问题时重复计算。以斐波那契数列为例：
int F(int n){
if(n==0||n==1) return 1;
else return F(n-1)+F(n-2);
}
然而上述代码会涉及很
...
PAT A1002 A+B for Polynomials
This time, you are supposed to find A+B where A and B are two polynomials.
Input Specification:
Each input file contains one test case. Each case occu
...
PAT A1001 A+B Format
Calculate a + b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less th
...