回溯解決爬樓梯問題

1.問題描述

每次爬樓梯有每次可跨1,2,3步，爬上一個N階樓梯有多少種方式，列印出每種方式。

2.源代碼

// ConsoleApplication6.cpp : 定義控制台應用程式的入口點。
//
#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <map>
using namespace std;

typedef std::vector<int> VecStep;
typedef std::map<int, VecStep> MapWay;

VecStep m_vecCanStep;
VecStep m_vecNextStep;
MapWay m_mapWay;
int iSum = 0;

void wayPrint()
{
  for (auto it = m_mapWay.begin(); it != m_mapWay.end(); it++)
  {
    int iSize = it->second.size();
    for (int i = 0; i < iSize; i++)
    {
      printf("%d ", it->second[i]);
    }
    printf("\n");
  }
}

void creep(int iLeftStep, int iNextStep, int iCnt)
{
  for (int i = 0; i < (int)m_vecCanStep.size(); i++)
  {
    if (iNextStep == m_vecCanStep[i])
    {
      int iStepSize = m_vecNextStep.size();
      if (iCnt >= iStepSize)
      {
        m_vecNextStep.push_back(iNextStep);
      }
      else if (iCnt < iStepSize)
      {
        m_vecNextStep[iCnt] = iNextStep;
      }
      iCnt++;
    }
  }
  if (iLeftStep == 0)
  {
    VecStep vecStep;
    for (int i = 0; i < iCnt; i++)
    {
      vecStep.push_back(m_vecNextStep[i]);
    }
    m_mapWay.insert(MapWay::value_type(iSum, vecStep));
    iSum++;
  }

  for (int i = 0; i < (int)m_vecCanStep.size(); i++)
  {
    if (iLeftStep - m_vecCanStep[i] >= 0)
    {
      creep(iLeftStep - m_vecCanStep[i], m_vecCanStep[i], iCnt);
    }
  }
}

void main()
{
  int iTotalStep = 0;
  int iNextStep = 0;                              
  int iStepCnt = 0;                           
  m_vecCanStep.push_back(1);
  m_vecCanStep.push_back(2);
  m_vecCanStep.push_back(3);

  scanf_s("%d", &iTotalStep);

  creep(iTotalStep, iNextStep,iStepCnt);
  wayPrint();
  printf("TotalWay = %d", iSum);
}      

3.代碼解析

m_vecCanStep：每次可以走的步數，插入1,2,3

m_vecNextStep：從0-iCnt為每種可以達到的N階的走法的步驟

m_mapWay：所有的走法

Creep形參含義：iLeftStep剩餘總階數，iNextStep下一步走法（1,2,3），iCnt目前走法已經走過的步驟統計

4.運作結果