动态规划（Dynamic Programming，简称DP）是一种解决多阶段决策过程最优化问题的数学方法。它通常用于解决那些具有重叠子问题和最优子结构性质的问题，这些问题可以分解为多个相互关联的子问题。
动态规划的核心思想是将原问题分解为较小的子问题，然后解决这些子问题，最后合并它们的解以获得原问题的最优解。这个方法通常涉及到创建一个表格或数组来存储子问题的解，以避免重复计算，从而提高算法效率。
关键特征和步骤：
-
重叠子问题：原问题可以分解为多个相似或相同的子问题，这些子问题可能需要多次解决。
-
最优子结构：问题的最优解可以通过子问题的最优解构建而成。
动态规划的一般步骤如下：
-
确定状态：定义问题的状态，通常用一些变量表示，以便描述问题的局部特征。
-
定义状态转移方程：找到子问题与原问题之间的关系，这可以通过递归式或迭代式来表示。
-
初始化：设置边界条件或初始状态，以确保算法能够正确地运行。
-
填表格或数组：计算并存储子问题的解，通常使用循环结构来填充表格或数组。
-
解决原问题：通常，最优解可以从填充的表格或数组中提取，以得到原问题的最优解。
动态规划常用于解决许多经典问题，如背包问题、最短路径问题、编辑距离、斐波那契数列等。
例题：给定三个数135，使用这三个数有多少种方式可以构造出一个指定的n（允许重复 允许不同顺序）
n=6
1+1+1+1+1+1 1+1+1+3
1+1+3+1 1+3+1+1
3+1+1+1 3+3
1+5 5+1
例如：dp【7】=dp【7-1】+dp【7-3】+dp【7-5】
不同路径
确定dp[i][j]为走到第i行第j列的总不同路径
递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
初始化：第一行和第一列全为1
确定顺序：从左到右从上到下
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m+1][n+1];for(int i = 1;i<n+1;i++){dp[1][i] = 1;}for(int i = 1;i<m+1;i++){dp[i][1] = 1;}for(int i = 2;i<m+1;i++){for(int j = 2;j<n+1;j++){// System.out.print(dp[i-1][j]+" ");dp[i][j] = dp[i-1][j] + dp[i][j-1];// System.out.print(dp[i][j]+" ");}// System.out.println();}return dp[m][n];}
}
