Leetcode-70. 爬楼梯
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 其中，1 <= n <= 45
递归（算法过大，超出时间限制）
代码语言：javascript复制 int climbStairs(int n)
{
if (n <= 2)
return n;
return climbStairs(n - 1) climbStairs(n - 2);
}动态规划，因为前两个的和可以表示第三个的结果。 我们首先想到，走上第三阶的方法，可以看成：1.走上第二阶之后再走一阶，2.走上第一阶之后再走两阶，所以我们的思路是动态规划，第三阶的走法是前两阶走法的总和；
代码语言：javascript复制 int climbStairs(int n)
{
//因为第一阶和第二阶可以直接表示，我们就直接返回
//从第三阶开始，我们可以用前两阶的和表示
//走上第三阶的方法，可以看成：
//1.走上第二阶之后再走一阶
//2.走上第一阶之后再走两阶
//所以第三阶的走法是前两阶走法的总和
if (n <= 2)
return n;
int dp[3];
dp[1] = 1;
dp[2] = 2;
int ret;
for (int i = 3; i <= n; i )
{
//这里每次进入循环证明还没结束，需要更新ret以及dp[2]和dp[1]的值
ret = dp[1] dp[2];
dp[1] = dp[2];
dp[2] = ret;
}
return dp[2];
}Leetcode-88. 合并两个有序数组
1.暴力求解 思路：直接将nums2的元素放到nums1的后面，直接排序
代码语言：javascript复制 int cmp(int* a, int* b)
{
return *a - *b;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
for (int i = 0; i != n; i)
{
nums1[m i] = nums2[i];
}
qsort(nums1, nums1Size, sizeof(int), cmp);
}2.逆向双指针
思路：两个指针分别从nums1和nums2的最后一个非0元素开始，tail从nums1的最后一个元素开始，nums1[i]与nums2[j]比较，谁大谁就移到nums[tail]中；还要考虑到nums1的元素或者nums2的元素已经走完的情况，谁先走完，就把另外一个数组的元素移到nums[tail]处；
代码语言：javascript复制 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
//i从nums1的最后一个非0元素开始遍历
//j从nums2的最后开始遍历
//tail从nums1的最后一个元素开始遍历
int i = m - 1, j = n - 1, tail = m n - 1;
while (i >= 0 || j >= 0)
{
//nums1的元素全部走完时，将nums2中的元素全部移到tail；
if (i == -1)
nums1[tail--] = nums2[j--];
//nums2的元素全部走完时，将nums2中的元素全部移到tail；
else if (j == -1)
nums1[tail--] = nums1[i--];
//谁大谁就移到tail处
else if (nums1[i] > nums2[j])
nums1[tail--] = nums1[i--];
else
nums1[tail--] = nums2[j--];
}
}
