第一题: 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
示例 3:
输入: m = 23, n = 12
输出: 193536720
public class Solution
{
private int _m;
private int _n;
public int UniquePaths(int m, int n)
{
_m = m;
_n = n;
int count = 0;
RecordPaths(0, 0, ref count);
return count;
}
private void RecordPaths(int i, int j, ref int count)
{
if (i == _m - 1 && j == _n - 1)
{
count++;
return;
}
if (i < _m)
{
RecordPaths(i + 1, j, ref count);
}
if (j < _n)
{
RecordPaths(i, j + 1, ref count);
}
}
}
第二题：爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
示例 3：
输入： 44
输出： 1134903170
使用for循环来实现
public class Solution {
public int ClimbStairs(int n) {
if (n <= 2)
return n;
int first = 1;
int second = 2;
int result = 0;
for (int i = 3; i <= n; i++)
{
result = first + second;
first = second;
second = result;
}
return result;
}
}
第三题：子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
子集扩展法：
public class Solution
{
public IList<IList<int>> Subsets(int[] nums)
{
IList<IList<int>> result = new List<IList<int>>();
IList<int> item = new List<int>();
result.Add(item);
for (int i = 0; i < nums.Length; i++)
{
for (int j = 0, len = result.Count; j < len; j++)
{
item = new List<int>(result[j]);
item.Add(nums[i]);
result.Add(item);
}
}
return result;
}
}
