一道笔试题求思路

是不是类似疯狂青蛙跳台阶的思路？

动态规划

转载 public class d11 {     static int[] a = new int[1000];     public static void main(String[] args) {         // TODO Auto-generated method stub         Scanner scanner = new Scanner(System.in);         while (scanner.hasNext()) {             int n = Integer.parseInt(scanner.nextLine());             a[0] = n;             cal(n, 1);         }     }     public static void cal(int n, int p) {         for (int i = n < a[p - 1] ? n : a[p - 1]; i > 0; i--) {             a[p] = i;             if (n == i) {                 System.out.printf("%d=%d", a[0], a[1]);                 for (int j = 2; j <= p; j++) {                     System.out.printf("+%d", a[j]);                 }                 System.out.println();             } else {                 cal(n - i, p + 1);             }         }     } }

#include <vector> #include <iostream> using namespace std; void dfs(int n,int sum,int s,vector<int>& res){     if(sum == n){         if(res.size()<=1){             return;         }         for_each(res.begin(),res.end(),[](int val){             cout<<val<<" ";         });         cout<<endl;         return;     }     for(int i = s;i<=n-sum;i++){         res.push_back(i);         dfs(n,sum+i,i,res);         res.pop_back();     } } int main() {     vector<int> v;     int n;     scanf("%d",&n);     dfs(n,0,1,v); }

递归，深度优先搜索

思路：深搜！

整数划分吧，递归

4＝1＋()的情况和2＋()的情况和3＋()的情况