回溯与递归

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

image

Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

---

思路：先看解集情况，很多现实问题都可以转化为树的形式，此处以“23”为例: 图示

解集可以从树的根部向下进行深度优先遍历，当遍历字符串的长度达到和数字一样的长度时，可以认为其时一个解。
对于这种树形的，不确定解情况的问题，回溯法时最好的方法。
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

回溯通过递归实现，但和递归具有明显的区别，回溯法从某一种可能出发，搜索所有可能的结果，之后再从另一种可能的点出发。达到搜索结果。
在理解回溯法之前，需要先理解递归。回溯需要有一个界限条件，此处就是当搜索到的结果等于数字长度时，认为时一个解。当一种可能的搜索路径结束之后，需要回到上一个回溯点，继续向前搜索，此处用tmp_result.pop_back()实现返回上一个搜索路径。

核心代码：

void back_tracking(std::vector<string> &result, string &digits,
                    int index, string &tmp_result,
                    std::vector<string> &phone_number){

    if(index==digits.length()){
        result.push_back(tmp_result);
        return;
    }

    for(int i=0; i<phone_number[digits[index]-'0'].length(); i++){
        tmp_result += phone_number[digits[index]-'0'][i];
        back_tracking(result,digits,index+1,tmp_result,phone_number);
        tmp_result.pop_back();
    }
}

代码：https://github.com/HCMY/UnCategoticalableAlgorithm/blob/master/Leetcode/BackTrack/Medium/letter_combination.cc

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

---

本题，一个机器人在一个矩阵的最右上角，它要达到最右下角的位置，只能向右或向下移动，不限制步长，求一共有多少种走法。
一开始很容易想到用回溯法来做，不过耗时很长，提交会导致TLE，通过构建递归树：

递归树，每个结点2个分支，向下走和向右走

这是一个2行3列的表，向下走行+1，向右走列+1。具体操作使用递归实现，递归结束的标志是行已经走完，或者列已经走完，递归出口，原路返回，不做操作，当行和列达到目标值(最终位置)时，路径计数+1

class Solution {
public:
    int uniquePaths(int m, int n) {
        int count = 0;
        func(1,1,n,m,count);
        return count;
    }

    void func(int right, int down, int rows, int cols, int &count){
        if(down==rows && right==cols)
            count++;
        if(down>rows || right>cols)
            return;

        if(right!=cols)
            func(right+1,down,rows,cols,count);
        if(down!=rows)
            func(right,down+1, rows,cols,count);
    }
};

使用动态规划实现

Unique Path