动态规划 4 步走

//动态规划 4 步走
// 1.确定状态，最后一步+分解为子问题
// 2.转移方程，根据子问题直接定义得到
// 3.初始条件 + 边界条件
// 4.计算顺序，避免重复计算
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<=0 || n<=0) return 0;
        //构建辅助数组
        int** dp=new int*[m];
        for(int i=0;i<m;i++)
            dp[i]=new int[n];
        //初始化
        dp[0][0]=1;

        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];
                }


            }
        }
        int result=dp[m-1][n-1];
        for(int i=0;i<m;i++)
            delete[] dp[i];
        delete[] dp;

        return result;

    }
};