62.不同路径

题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

思路：本题采用递归的方法思路比较简单，但会超出时间限制。故而采用动态规划的方法。切入点在于，当m和n之中存在一个为1，则只有一种走法。
代码如下：

public class Solution
{
    public int UniquePaths(int m, int n)
    {
        int[,] dp=new int[m,n];
        for(int i=0;i<m;i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0 || j == 0)
                    dp[i, j] = 1;
                else
                    dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            }
        }
        return dp[m - 1, n - 1];
    }
}

70.爬楼梯

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

思路：通过找规律，可以发现这其实是一道斐波那契数列问题，采用递归会超出时间限制，故采用循环。
代码如下:

public class Solution
{
    public int ClimbStairs(int n)
    {
        if(n<=2)
            return n;
        int one = 1;
        int two = 2;
        int result=0;
        for (int i = 3; i < n+1; i++)
        {
            result = one + two;
            one = two;
            two = result;
        }
        return result;
    }
}

78.子集

题目描述：给你一个整数数组 nums ，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

思路：子集拓展法：先放入空集，在空集的基础上，每扩展一个数字算一个新子集，依次类推。
代码如下：

public class Solution
{
    public IList<IList<int>> Subsets(int[] nums)
    {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> item = new List<int>();
        result.Add(item);
        if (nums.Length == 0)
            return result;
        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;
    }
}